TY - JOUR
T1 - Stochastic binary problems with simple penalties for capacity constraints violations
AU - Fortz, B.
AU - Labbé, M.
AU - Louveaux, F.
AU - Poss, M.
PY - 2013/4/1
Y1 - 2013/4/1
N2 - 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 strictly positively distributed 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.
AB - 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 strictly positively distributed 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.
KW - Branch-and-cut algorithm
KW - Knapsack problem
KW - Mixed-integer non-linear programming
KW - Pseudo-polynomial algorithm
KW - Stochastic programming
UR - http://www.scopus.com/inward/record.url?scp=84875435973&partnerID=8YFLogxK
U2 - 10.1007/s10107-012-0520-4
DO - 10.1007/s10107-012-0520-4
M3 - Article
AN - SCOPUS:84875435973
SN - 0025-5610
VL - 138
SP - 199
EP - 221
JO - Mathematical Programming
JF - Mathematical Programming
IS - 1-2
ER -