Løkketangen, Arne; Woodruff, David L. Progressive hedging and tabu search applied to mixed integer (0,1) multistage stochastic programming. (English) Zbl 0869.90056 J. Heuristics 2, No. 2, 111-128 (1996). Summary: 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. Cited in 50 Documents MSC: 90C15 Stochastic programming 90C09 Boolean programming 90C11 Mixed integer programming Keywords:multistage decision process; multistage, stochastic mixed-integer \((0,1)\) programming; progressive hedging; tabu search Software:MINOS PDFBibTeX XMLCite \textit{A. Løkketangen} and \textit{D. L. Woodruff}, J. Heuristics 2, No. 2, 111--128 (1996; Zbl 0869.90056) Full Text: DOI