Approximated perspective relaxations: a project and lift approach

Antonio Frangioni (), Fabio Furini () and Claudio Gentile ()

Computational Optimization and Applications, 2016, vol. 63, issue 3, 705-735

Abstract: The perspective reformulation (PR) of a Mixed-Integer NonLinear Program with semi-continuous variables is obtained by replacing each term in the (separable) objective function with its convex envelope. Solving the corresponding continuous relaxation requires appropriate techniques. Under some rather restrictive assumptions, the Projected PR ( $$\mathrm{P}^2\mathrm{R}$$ P 2 R ) can be defined where the integer variables are eliminated by projecting the solution set onto the space of the continuous variables only. This approach produces a simple piecewise-convex problem with the same structure as the original one; however, this prevents the use of general-purpose solvers, in that some variables are then only implicitly represented in the formulation. We show how to construct an Approximated Projected PR ( $$\mathrm{AP}^2\mathrm{R}$$ AP 2 R ) whereby the projected formulation is “lifted” back to the original variable space, with each integer variable expressing one piece of the obtained piecewise-convex function. In some cases, this produces a reformulation of the original problem with exactly the same size and structure as the standard continuous relaxation, but providing substantially improved bounds. In the process we also substantially extend the approach beyond the original $$\mathrm{P}^2\mathrm{R}$$ P 2 R development by relaxing the requirement that the objective function be quadratic and the left endpoint of the domain of the variables be non-negative. While the $$\mathrm{AP}^2\mathrm{R}$$ AP 2 R bound can be weaker than that of the PR, this approach can be applied in many more cases and allows direct use of off-the-shelf MINLP software; this is shown to be competitive with previously proposed approaches in some applications. Copyright Springer Science+Business Media New York 2016

Keywords: Mixed-integer nonlinear problems; Semi-continuous variables; Perspective reformulation; Projection; 90C06; 90C25 (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10589-015-9787-8 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:63:y:2016:i:3:p:705-735

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-015-9787-8

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().