  


Chanceconstrained binary packing problems
Yongjia Song (ysong29wisc.edu) Abstract: We consider a class of packing problems with uncertain data, which we refer to as the chanceconstrained 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 chanceconstrained knapsack and set packing problems with random coefficients. Assuming a general distribution, we propose a problem formulation in its original space based on the socalled 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: Chanceconstrained optimization, integer programming Category 1: Stochastic Programming Category 2: Integer Programming Citation: Submitted for publication Download: [PDF] Entry Submitted: 10/13/2012 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  