Solving multiple scenarios in a combinatorial auction

As part of its social policy, the government of Chile provides more than 1.8 million meals daily to public schoolchildren under the authority of junta Nacional de Auxilio Escolar y Becas (JUNAEB), the state agency responsible for the program, at an annual cost of 360 million dollars. The service is provided by private firms chosen through an annual public auction. In order to capture economies of scale, a combinatorial auction design is implemented, allowing suppliers to bid on different sets of geographical units within the country. The bid evaluation process must solve multiple scenarios of a difficult combinatorial optimization model. To date, more than 2 billion dollars have been awarded under this methodology. In this paper, we describe the 2006 auction process and report that solution times can be significantly improved if the scenarios are solved in an appropriate order and the optimal solution to one scenario is employed as the initial solution of another. Results reflecting these improvements are given for real instances of the 2006 auction. (C) 2008 Elsevier Ltd. All rights reserved.