Projected Perspective Reformulations with Applications in Design Problems

Antonio Frangioni (), Claudio Gentile (), Enrico Grande () and Andrea Pacifici ()
Additional contact information
Antonio Frangioni: Dipartimento di Informatica, Università di Pisa, Polo Universitario della Spezia, 19121 La Spezia, Italy
Claudio Gentile: Istituto di Analisi dei Sistemi ed Informatica “A. Ruberti”---CNR, 00185 Rome, Italy
Enrico Grande: Dipartimento di Ingegneria dell'Impresa, Università degli Studi di Roma “Tor Vergata,” 00133 Rome, Italy
Andrea Pacifici: Dipartimento di Ingegneria dell'Impresa, Università degli Studi di Roma “Tor Vergata,” 00133 Rome, Italy

Operations Research, 2011, vol. 59, issue 5, 1225-1232

Abstract: The perspective relaxation (PR) is a general approach for constructing tight approximations to mixed-integer nonlinear programs (MINLP) with semicontinuous variables. The PR of a MINLP can be formulated either as a mixed-integer second-order cone program (MI-SOCP), provided that the original objective function is SOCP-representable, or as a semi-infinite MINLP. In this paper, we show that under some further assumptions (rather restrictive, but satisfied in several practical applications), the PR of a mixed-integer quadratic program (MIQP) can also be reformulated as a piecewise-quadratic program (QP), ultimately yielding a QP relaxation of roughly the same size of the standard continuous relaxation. Furthermore, if the original problem has some exploitable structure, then this structure is typically preserved in the reformulation, thus allowing the construction of specialized approaches for solving the PR. We report on implementing these ideas on two MIQPs with appropriate structure: a sensor placement problem and a quadratic-cost (single-commodity) network design problem.

Keywords: mixed-integer nonlinear programming problems; semicontinuous variables; perspective relaxation; sensor placement problem; network design problem (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1110.0930 (application/pdf)

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:inm:oropre:v:59:y:2011:i:5:p:1225-1232

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().