Stochastic set packing problem

Stochastic set packing problem

0.00 Avg rating0 Votes
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: , ,
Keywords: programming: integer
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.