On the mixing set with a knapsack constraint

• 成果类型: Article
• 署名作者: Abdi, Ahmad; Fukasawa, Ricardo
• 署名单位: University of Waterloo
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-0979-5
• 发表日期: 2016
• 页码: 191-217
• 关键词: relaxations; PROGRAMS; facets

摘要

We study a substructure appearing in mixed-integer programming reformulations of chance-constrained programs with stochastic right-hand-sides over a finite discrete distribution, which we call the mixing set with a knapsack constraint. Recently, Luedtke et al. (Math. Program. 122(2):247-272, 2010) and KuA A1/4kyavuz (Math Program 132(1):31-56, 2012) studied valid inequalities for such sets. However, most of their results were focused on the equal probabilities case (when the knapsack constraint reduces to a cardinality constraint). In this paper, we focus on the general probabilities case (general knapsack constraint). We characterize the valid inequalities that do not come from the knapsack polytope and use this characterization to generalize the results previously derived for the equal probabilities case. Our results allow for a deep understanding of the relationship that the set under consideration has with the knapsack polytope. Moreover, they allow us to establish benchmarks that can be used to identify when a relaxation will be useful for the considered types of reformulations of chance-constrained programs.