Affordable Access

Access to the full text

Strengthening the sequential convex MINLP technique by perspective reformulations

Authors
  • D’Ambrosio, Claudia1
  • Frangioni, Antonio2
  • Gentile, Claudio3
  • 1 LIX UMR 7161, École Polytechnique, Route de Saclay, Palaiseau, 91128, France , Palaiseau (France)
  • 2 Università di Pisa, Dipartimento di Informatica, Largo B. Pontecorvo 3, Pisa, 56127, Italy , Pisa (Italy)
  • 3 Istituto di Analisi dei Sistemi ed Informatica “Antonio Ruberti”, Consiglio Nazionale delle Ricerche, Via dei Taurini 19, Rome, 00185, Italy , Rome (Italy)
Type
Published Article
Journal
Optimization Letters
Publisher
Springer Berlin Heidelberg
Publication Date
Nov 23, 2018
Volume
13
Issue
4
Pages
673–684
Identifiers
DOI: 10.1007/s11590-018-1360-9
Source
Springer Nature
Keywords
License
Yellow

Abstract

The sequential convex MINLP (SC-MINLP) technique is a solution method for nonconvex mixed-integer nonlinear problems (MINLPs) where the nonconvexities are separable. It is based on solving a sequence of convex MINLPs which trade a better and better relaxation of the nonconvex part of the problem with the introduction of more and more piecewise-linear nonconvex terms, and therefore binary variables. The convex MINLPs are obtained by partitioning the domain of each separable nonconvex term in the intervals in which it is convex and those in which it is concave. In the former, the term is left in its original form, while in the latter it is piecewise-linearized. Since each interval corresponds to a semi-continuous variable, we propose to modify the convex terms using the Perspective Reformulation technique to strengthen the bounds. We show by means of experimental results on different classes of instances that doing so significantly decreases the solution time of the convex MINLPs, which is the most time consuming part of the approach, and has therefore the potential to improving the overall effectiveness of SC-MINLP.

Report this publication

Statistics

Seen <100 times