Lagrangian decomposition and mixed-integer quadratic programming reformulations for probabilistically constrained quadratic programs

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

17 Scopus Citations
View graph of relations

Author(s)

  • Xiaojin Zheng
  • Xiaoling Sun
  • Duan Li
  • Xueting Cui

Detail(s)

Original languageEnglish
Pages (from-to)38-48
Journal / PublicationEuropean Journal of Operational Research
Volume221
Issue number1
Online published13 Mar 2012
Publication statusPublished - 16 Aug 2012
Externally publishedYes

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)