Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems |
| |
Authors: | Jean-Paul Watson David L Woodruff |
| |
Institution: | 1. Discrete Math and Complex Systems Department, Sandia National Laboratories, P.O. Box 5800, MS 1318, Albuquerque, NM, 87185-1318, USA 2. Graduate School of Management, University of California, Davis, CA, 95616-8609, USA
|
| |
Abstract: | Numerous planning problems can be formulated as multi-stage stochastic programs and many possess key discrete (integer) decision
variables in one or more of the stages. Progressive hedging (PH) is a scenario-based decomposition technique that can be leveraged
to solve such problems. Originally devised for problems possessing only continuous variables, PH has been successfully applied
as a heuristic to solve multi-stage stochastic programs with integer variables. However, a variety of critical issues arise
in practice when implementing PH for the discrete case, especially in the context of very difficult or large-scale mixed-integer
problems. Failure to address these issues properly results in either non-convergence of the heuristic or unacceptably long
run-times. We investigate these issues and describe algorithmic innovations in the context of a broad class of scenario-based
resource allocation problem in which decision variables represent resources available at a cost and constraints enforce the
need for sufficient combinations of resources. The necessity and efficacy of our techniques is empirically assessed on a two-stage
stochastic network flow problem with integer variables in both stages. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|