Lagrangian Decomposition for large-scale two-stage stochastic mixed 0-1 problems

  1. L.F. Escudero 1
  2. M.A. Garín 2
  3. G. Pérez 2
  4. A. Unzueta 2
  1. 1 Universidad Rey Juan Carlos, España
  2. 2 Universidad del País Vasco, España
Revue:
Top

ISSN: 1863-8279,  1134-5764

Année de publication: 2012

Volumen: 20

Número: 2

Pages: 347-374

Type: Article

DIALNET GOOGLE SCHOLAR

D'autres publications dans: Top

Résumé

In this paper we study solution methods for solving the dual problem corresponding to the Lagrangian Decomposition of two-stage stochastic mixed 0-1 models. We represent the two-stage stochastic mixed 0-1 problem by a splitting variable representation of the deterministic equivalent model, where 0-1 and continuous variables appear at any stage. Lagrangian Decomposition (LD) is proposed for satisfying both the integrality constraints for the 0-1 variables and the non-anticipativity constraints. We compare the performance of four iterative algorithms based on dual Lagrangian Decomposition schemes: the Subgradient Method, the Volume Algorithm, the Progressive Hedging Algorithm, and the Dynamic Constrained Cutting Plane scheme. We test the tightness of the LD bounds in a testbed of medium- and large-scale stochastic instances.

€ Voir financement

Information sur le financement

Acknowledgements This research has been partially supported by the projects ECO2008-00777 ECON from the Ministry of Education and Science, Grupo de Investigación IT-347-10 from the Basque Government, grant FPU ECO-2006 from the Ministry of Education and Science, grants RM URJC-CM-2008-CET-3703 and RIESGOS CM from Comunidad de Madrid, and PLANIN MTM2009-14087-C04-01 from Ministry of Science and Innovation, Spain. We would like to express our gratefulness to Prof. Dr. F. Tusell for making easier the access to the Laboratory of Quantitative Economics (Economic Sciences School, UPV/EHU) to perform and check the computing experience.

Financeurs

La source de données: Dialnet