A polyhedral study on chance constrained program with random right-hand side

• 成果类型: Article
• 署名作者: Zhao, Ming; Huang, Kai; Zeng, Bo
• 署名单位: University of Houston System; University of Houston; McMaster University; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1103-6
• 发表日期: 2017
• 页码: 19-64
• 关键词: mixed-integer inequalities; p-efficient points; probabilistic constraints; discrete-distributions; convex approximations; optimization problems; random-variables; bundle methods; mixing set; optimality

摘要

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.