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.