The Perspective Relaxation (PR) is a general approach for constructing tight approximations to Mixed Integer Non Linear Programs (MINLP) with semicontinuous variables. The PR of a MINLP can be formulated either as a Mixed Integer Second Order Cone Program (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 can also be reformulated as a piecewise quadratic problem, 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.

Projected Perspective Reformulations with Applications in Design Problems

FRANGIONI, ANTONIO;
2011-01-01

Abstract

The Perspective Relaxation (PR) is a general approach for constructing tight approximations to Mixed Integer Non Linear Programs (MINLP) with semicontinuous variables. The PR of a MINLP can be formulated either as a Mixed Integer Second Order Cone Program (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 can also be reformulated as a piecewise quadratic problem, 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.
2011
Frangioni, Antonio; C., Gentile; E., Grande; A., Pacifici
File in questo prodotto:
File Dimensione Formato  
ProjectedPC.pdf

accesso aperto

Descrizione: Documento in Post-print
Tipologia: Documento in Post-print
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 201.56 kB
Formato Adobe PDF
201.56 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/144243
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 29
  • ???jsp.display-item.citation.isi??? 29
social impact