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

L.F. Escudero ^[1] ; M.A. Garín ^[2] ; G. Pérez ^[2] ; A. Unzueta ^[2]
1. [1] Universidad Rey Juan Carlos
  
  Universidad Rey Juan Carlos
  
  Madrid, España
2. [2] Universidad del País Vasco/Euskal Herriko Unibertsitatea
  
  Universidad del País Vasco/Euskal Herriko Unibertsitatea
  
  Leioa, España
Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 20, Nº. 2, 2012, págs. 347-374
Idioma: inglés
Enlaces
- Texto completo (pdf)
Resumen
- 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.