Easy distributions for combinatorial optimization problems with probabilistic constraints

Bernard Fortz (1) , Michael Poss (2)

1 GOM - Graphes et Optimisation Mathématique [Bruxelles]
2 Heudiasyc - Heuristique et Diagnostic des Systèmes Complexes [Compiègne]

We show how we can linearize individual probabilistic linear constraints with binary variables when all coefficients are independently distributed according to either N(μi,λμi), for some λ>0 and μi>0, or Γ(ki,θ) for some θ>0 and ki>0. The constraint can also be linearized when the coefficients are independent and identically distributed and either positive or strictly stable random variables. © 2010 Elsevier B.V. All rights reserved.

Mots clés: Stochastic programming; combinatorial optimization; probabilistic constraint

Domaines: Recherche opérationnelle [math.OC]

Bernard Fortz, Michael Poss. Easy distributions for combinatorial optimization problems with probabilistic constraints. Operations Research Letters, 2010, 38 (6), pp.545-549. ⟨10.1016/j.orl.2010.09.005⟩. ⟨hal-01255270⟩