ISSN:
1572-9397
Keywords:
stochastic programming
;
integer programming
;
progressive hedging
;
tabu search
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract Many problems faced by decision makers are characterized by a multistage decision process with uncertainty about the future and some decisions constrained to take on values of either zero or one (for example, either open a facility at a location or do not open it). Although some mathematical theory exists concerning such problems, no general-purpose algorithms have been available to address them. In this article, we introduce the first implementation of general purpose methods for finding good solutions to multistage, stochastic mixed-integer (0, 1) programming problems. The solution method makes use of Rockafellar and Wets' progressive hedging algorithm that averages solutions rather than data. Solutions to the induced quadratic (0,1) mixed-integer subproblems are obtained using a tabu search algorithm. We introduce the notion of integer convergence for progressive hedging. Computational experiments verify that the method is effective. The software that we have developed reads standard (SMPS) data files.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00247208
Permalink