×

Progressive hedging and tabu search applied to mixed integer (0,1) multistage stochastic programming. (English) Zbl 0869.90056

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.

MSC:

90C15 Stochastic programming
90C09 Boolean programming
90C11 Mixed integer programming

Software:

MINOS
PDFBibTeX XMLCite
Full Text: DOI