Optimization Online


Stochastic binary problems with simple penalties for capacity constraints violations

B Fortz (bfortz***at***ulb.ac.be)
M Labbe (mlabbe***at***ulb.ac.be)
F Louveaux (francois.louveaux***at***fundp.ac.be)
M Poss (mposs***at***ulb.ac.be)

Abstract: This paper studies stochastic programs with first-stage binary variables and capacity constraints, using simple penalties for capacities violations. In particular, we take a closer look at the knapsack problem with weights and capacity following independent random variables and prove that the problem is weakly \NP-hard in general. We provide pseudo-polynomial algorithms for three special cases of the problem: constant weights and capacity uniformly distributed, subset sum with Gaussian weights and arbitrary random capacity, and subset sum with constant weights and arbitrary random capacity. We then turn to a branch-and-cut algorithm based on the outer approximation of the objective function. We provide computational results for the stochastic knapsack problem (i) with Gaussian weights and constant capacity and (ii) with constant weights and capacity uniformly distributed, on randomly generated instances inspired by computational results for the knapsack problem.

Keywords: tochastic programming, Knapsack problem, Pseudo-polynomial algorithm, Mixed-integer non-linear programming, Branch-and-cut algorithm

Category 1: Stochastic Programming

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation: ULB, March 2009.

Download: [PDF]

Entry Submitted: 03/24/2009
Entry Accepted: 03/24/2009
Entry Last Modified: 01/29/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