Lagrangian decomposition and mixed-integer quadratic programming reformulations for probabilistically constrained quadratic programs
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 38-48 |
Journal / Publication | European Journal of Operational Research |
Volume | 221 |
Issue number | 1 |
Online published | 13 Mar 2012 |
Publication status | Published - 16 Aug 2012 |
Externally published | Yes |
Link(s)
Abstract
Probabilistically constrained quadratic programming (PCQP) problems arise naturally from many real-world applications and have posed a great challenge in front of the optimization society for years due to the nonconvex and discrete nature of its feasible set. We consider in this paper a special case of PCQP where the random vector has a finite discrete distribution. We first derive second-order cone programming (SOCP) relaxation and semidefinite programming (SDP) relaxation for the problem via a new Lagrangian decomposition scheme. We then give a mixed integer quadratic programming (MIQP) reformulation of the PCQP and show that the continuous relaxation of the MIQP is exactly the SOCP relaxation. This new MIQP reformulation is more efficient than the standard MIQP reformulation in the sense that its continuous relaxation is tighter than or at least as tight as that of the standard MIQP. We report preliminary computational results to demonstrate the tightness of the new convex relaxations and the effectiveness of the new MIQP reformulation.
Research Area(s)
- Mixed-integer quadratic program reformulation, Probabilistic constraint, Quadratic programming, Second-order cone programming relaxation, Semidefinite program relaxation
Citation Format(s)
Lagrangian decomposition and mixed-integer quadratic programming reformulations for probabilistically constrained quadratic programs. / Zheng, Xiaojin; Sun, Xiaoling; Li, Duan et al.
In: European Journal of Operational Research, Vol. 221, No. 1, 16.08.2012, p. 38-48.
In: European Journal of Operational Research, Vol. 221, No. 1, 16.08.2012, p. 38-48.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review