Chance-constrained binary packing problems

Yongjia Song*, James R. Luedtke, Simge Küçükyavuz

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

44 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)735-747
Number of pages13
JournalINFORMS Journal on Computing
Volume26
Issue number4
DOIs
StatePublished - Sep 1 2014

Keywords

  • Chance-constrained stochastic programming
  • Integer programming

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'Chance-constrained binary packing problems'. Together they form a unique fingerprint.

Cite this