Optimization Online


A Polyhedral Study on Chance Constrained Program with Random Right-Hand Side

Ming Zhao (mzhao***at***bauer.uh.edu)
Kai Huang (khuang***at***mcmaster.ca)
Bo Zeng (bzeng***at***pitt.edu)

Abstract: The essential structure of the mixed--integer programming formulation for chance--constrained program (CCP) is the intersection of multiple mixing sets with a $0-1$ knapsack. To improve our computational capacity on CCP, an underlying substructure, the (single) mixing set with a $0-1$ knapsack, has received substantial attentions recently. In this study, we consider a CCP problem with stochastic right--hand side under a finite discrete distribution. We first present a family of strong inequalities that subsumes known facet-defining ones for that single mixing set. Due to the flexibility of our generalized inequalities, we develop a new separation heuristic that has a complexity much less than existing one and guarantees generated cutting planes are facet--defining for the polyhedron of CCP. Then, we study lifting and superadditive lifting on knapsack cover inequalities, and provide an implementable procedure on deriving another family of strong inequalities for the single mixing set. Finally, different from the traditional approach that aggregates original constraints to investigate polyhedral implications due to their interactions, we propose a novel blending procedure that produces strong valid inequalities for CCP by integrating those derived from individual mixing sets. We show that, under certain conditions, they are the first type of facet-defining inequalities describing intersection of multiple mixing sets, and design an efficient separation heuristic for implementation. In the computational experiments, we perform a systematic study and illustrate the efficiency of the proposed inequalities on solving chance constrained static probabilistic lot-sizing problems.

Keywords: Mixed--integer programming,Chance constraints, Mixing set, Knapsack, Lifting, Blending

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Stochastic Programming

Category 3: Integer Programming (Cutting Plane Approaches )

Citation: Article to appear in Mathematical Programming.

Download: [PDF]

Entry Submitted: 05/01/2016
Entry Accepted: 05/01/2016
Entry Last Modified: 12/08/2016

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