Chance-Constrained Binary Packing Problems
- 1 November 2014
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 26 (4) , 735-747
Abstract
We consider a class of packing problems with uncertain data, which we refer to as the chance-constrained binary packing problem. In this problem, a subset of items is selected that maximizes the total profit so that a generic packing constraint is satisfied with high probability. Interesting special cases of our problem include chance-constrained knapsack and set packing problems with random coefficients. We propose a problem formulation in its original space based on the so-called probabilistic covers. We focus our solution approaches on the special case in which the uncertainty is represented by a finite number of scenarios. In this case, the problem can be formulated as an integer program by introducing a binary decision variable to represent feasibility of each scenario. We derive a computationally efficient coefficient strengthening procedure for this formulation, and demonstrate how the scenario variables can be efficiently projected out of the linear programming relaxation. We also study how methods for lifting deterministic cover inequalities can be leveraged to perform approximate lifting of probabilistic cover inequalities. We conduct an extensive computational study to illustrate the potential benefits of our proposed techniques on various problem classes.Keywords
This publication has 37 references indexed in Scilit:
- Capital rationing problems under uncertainty and riskComputational Optimization and Applications, 2011
- Robust Optimization2009
- An exact approach for solving integer problems under probabilistic constraints with random technology matrixAnnals of Operations Research, 2009
- The submodular knapsack polytopeDiscrete Optimization, 2009
- Embedding {0, ½}-Cuts in a Branch-and-Cut Framework: A Computational StudyINFORMS Journal on Computing, 2007
- Sequence Independent Lifting for Mixed-Integer ProgrammingOperations Research, 2004
- Uncertain convex programs: randomized solutions and confidence levelsMathematical Programming, 2004
- The Probabilistic Set-Covering ProblemOperations Research, 2002
- OR-Library: Distributing Test Problems by Electronic MailJournal of the Operational Research Society, 1990
- Facets of the Knapsack Polytope From Minimal CoversSIAM Journal on Applied Mathematics, 1978