Stochastic binary problems with simple penalties for capacity constraints violations

B. Fortz, M. Labbé, F. Louveaux, M. Poss

Résultats de recherche: Contribution à un journal/une revueArticle

Résumé

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.

langue originaleAnglais
Pages (de - à)199-221
Nombre de pages23
journalMathematical Programming
Volume138
Numéro de publication1-2
Les DOIs
étatPublié - 1 avr. 2013

Empreinte digitale

Capacity Constraints
Penalty
Binary
Random variables
Knapsack Problem
Subset Sum
Polynomials
Computational Results
Outer Approximation
Branch-and-cut
Binary Variables
Polynomial Algorithm
Independent Random Variables
Strictly
NP-complete problem
Objective function
Arbitrary

Citer ceci

Fortz, B. ; Labbé, M. ; Louveaux, F. ; Poss, M. / Stochastic binary problems with simple penalties for capacity constraints violations. Dans: Mathematical Programming. 2013 ; Vol 138, Numéro 1-2. p. 199-221.
@article{c26bc003ac434c0ca606ce25b910ea5b,
title = "Stochastic binary problems with simple penalties for capacity constraints violations",
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 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.",
keywords = "Branch-and-cut algorithm, Knapsack problem, Mixed-integer non-linear programming, Pseudo-polynomial algorithm, Stochastic programming",
author = "B. Fortz and M. Labb{\'e} and F. Louveaux and M. Poss",
year = "2013",
month = "4",
day = "1",
doi = "10.1007/s10107-012-0520-4",
language = "English",
volume = "138",
pages = "199--221",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer-Verlag GmbH and Co. KG",
number = "1-2",

}

Stochastic binary problems with simple penalties for capacity constraints violations. / Fortz, B.; Labbé, M.; Louveaux, F.; Poss, M.

Dans: Mathematical Programming, Vol 138, Numéro 1-2, 01.04.2013, p. 199-221.

Résultats de recherche: Contribution à un journal/une revueArticle

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

VL - 138

SP - 199

EP - 221

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1-2

ER -