Optimization Online


Chance-constrained binary packing problems

Yongjia Song (ysong29***at***wisc.edu)
James Luedtke (jrluedt1***at***wisc.edu)
Simge Kucukyavuz (kucukyavuz.2***at***osu.edu)

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. Assuming a general distribution, 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: Chance-constrained optimization, integer programming

Category 1: Stochastic Programming

Category 2: Integer Programming

Citation: Submitted for publication

Download: [PDF]

Entry Submitted: 10/13/2012
Entry Accepted: 10/14/2012
Entry Last Modified: 12/19/2013

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