Article ID: | iaor20112262 |
Volume: | 211 |
Issue: | 2 |
Start Page Number: | 232 |
End Page Number: | 240 |
Publication Date: | Jun 2011 |
Journal: | European Journal of Operational Research |
Authors: | Landete Mercedes, Escudero Laureano F, Rodrguez-Cha Antonio M |
Keywords: | programming: integer |
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.