Optimization Online


Strong Inequalities for Chance-Constrained Program

Ming Zhao (mr.ming.zhao***at***gmail.com)
Kai Huang (khuang***at***mcmaster.ca)
Bo Zeng (bzeng***at***usf.edu)

Abstract: As an essential substructure underlying a large class of chance-constrained programming problems with finite discrete distributions, the mixing set with $0-1$ knapsack has received considerable attentions in recent literature. In this study, we present a family of strong inequalities that subsume existing ones for this set. We also find many other inequalities that can be explained by lifting on $0-1$ knapsack with continuous variable restrained in piecewise intervals. To develop stronger inequalities for the original chance-constraint model, earlier studies consider a relaxation of the intersection of multiple mixing sets by aggregating individual mixing sets into a single mixing set. Then, non-trivial inequalities can be generated from such resulting single mixing set. Nevertheless, it is unknown that if this procedure will derive facet-defining inequalities for the intersection of multiple mixing sets. Different from such traditional formulation aggregation strategy, we propose a new blending procedure that can produce strong inequalities by combining valid inequalities from individual mixing sets. We further show that those inequalities are facet-defining under certain conditions.

Keywords: polyhedral study, chance-constrained program, mixing set

Category 1: Integer Programming

Category 2: Integer Programming (Cutting Plane Approaches )


Download: [PDF]

Entry Submitted: 11/08/2014
Entry Accepted: 11/08/2014
Entry Last Modified: 08/16/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society