Strong Inequalities for Chance-Constrained Program

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.

Article

Download

View PDF