Projected Perspective Reformulations with Applications in Design Problems

• 成果类型: Article
• 署名作者: Frangioni, Antonio; Gentile, Claudio; Grande, Enrico; Pacifici, Andrea
• 署名单位: University of Pisa; Consiglio Nazionale delle Ricerche (CNR); University of Rome Tor Vergata
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1110.0930
• 发表日期: 2011
• 页码: 1225-1232
• 关键词: Optimization; relaxation; PROGRAMS; algorithm; cuts

摘要

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.