Stochastic set packing problem
In this paper a stochastic version of the set packing problem (SPP), is studied via scenario analysis. We consider a one-stage recourse approach to deal with the uncertainty in the coefficients. It consists of maximizing in the stochastic SPP a composite function of the expected value minus the weighted risk of obtaining a scenario whose objective function value is worse than a given threshold. The splitting variable representation is decomposed by dualizing the nonanticipativity constraints that link the deterministic SPP with a 0-1 knapsack problem for each scenario under consideration. As a result a (structured) larger pure 0-1 model is created. We present several procedures for obtaining good feasible solutions, as well as a preprocessing approach for fixing variables. The Lagrange multipliers updating is performed by using the Volume Algorithm. Computational experience is reported for a broad variety of instances, which shows that the new approach usually outperforms a state-of-the-art optimization engine, producing a comparable optimality gap with smaller (several orders of magnitude) computing time.
Year of publication: |
2011
|
---|---|
Authors: | Escudero, Laureano F. ; Landete, Mercedes ; Rodríguez-Chía, Antonio M. |
Published in: |
European Journal of Operational Research. - Elsevier, ISSN 0377-2217. - Vol. 211.2011, 2, p. 232-240
|
Publisher: |
Elsevier |
Keywords: | Assignment Set packing Stochastic 0-1 programming Simple recourse Lagrangian decomposition Volume Algorithm |
Saved in:
Online Resource
Saved in favorites
Similar items by person
-
Stochastic set packing problem
Escudero, Laureano F., (2011)
-
Stochastic set packing problem
Escudero, Laureano F., (2011)
-
Landete, Mercedes, (2013)
- More ...