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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aboudi, R., and K. Jörnsten, (1994). “Tabu Search for General Zero-One Integer Programs Using the Pivot and Complement Heuristic.” ORSA Journal on Computing 6, 82–93.
Averbakh, I.L., (1990). “An Additive Method for Optimization of Two-Stage Stochastic Systems with Discrete Variables.” Soviet Journal of Computer and System Sciences 28, 161–165.
Balas, E., and C. Martin. (1980). “Pivot and Complement: Heuristic for 0–1 Programming.” Management Science 26, 86–96.
Bertsekas, D.P. (1982). Constrained Optimization and Lagrange Multiplier Methods. New York: Academic Press.
Birge, J.R., M.A. Dempster, H.I. Gassman, E.A. Gunn, A.J King, and S.W. Wallace. (1987). “A Standard Input Format for Multiperiod Stochastic Linear Program.” COAL (Math. Prog. Soc., Comm. on Algorithms) Newsletter 17, 1–19.
CPLEX Optimization, Inc. (1994). Using the CPLEX Callable Library. CPLEX Optimization, Inc., Suite 279, 930 Tahoe Blvd. Building 802, Incline Village, NV 89451–9436.
Fourer, R., D.M. Gay, and B.W. Kerninghan (1993). AmPL. San Francisco: Scientific Press.
Gassman, H.I., and E. Schweitzer (1996). “Proposed Extensions to the SMPS Input Format for Stochastic Linear Programs.” WP-96–1, School of Business, Dalhousie University, Halifax, Canada.
Glover, F. (1989). “Tabu Search—Part I.” ORSA Journal on Computing 1, 190–206.
Glover, F., and M. Laguna. (1993). “Tabu Search.” In C. Reeves (Ed.), Modern Heuristics for Combinatorial Problems. Blackwell Scientific Publishing.
Glover, F., M. Laguna, E. Taillard, and D. de Werra (Eds.). (1993). Annals of Operations Research 41.
Glover, F., and A. Løkketangen. (1995). “Solving Zero-One Mixed Integer Programming Problems Using Tabu Search.” Technical Report, Molde College, 6400 Molde Norway.
Helgason, T., and S.W. Wallace. (1991). “Approximate Scenario Solutions in the Progressive Hedging Algorithm: A Numerical Study with an Application to Fisheries Management.” Annals of OR 30, 425–444.
Jorjani, S., C.H. Scott, and D.L. Woodruff. (1995). “Selection of and Optimal Subset of Sizes.” Technical Report, GSM, UC Irvine, Irvine, CA.
King, A.J. (1994). “SP/OSL Version 1.0 Stochastic Programming Interface Library User's Guide.” IBM Research Division, T.J. Watson Research Center, Yorktown Heights, NY 10598.
Laporte, G., and F.V. Louveaux. (1993). “The Integer L-Shaped Method for Stochastic Integer Programs with Complete Recourse.” OR Letters 13, 133–142.
Løkketangen, A., and F. Glover. (1996). “Probabilistic Move Selection in Tabu Search for Zero-One Mixed Integer Programming Problems.” In Metaheuristics: Theory and Applications, 1995. Kluwer.
Løkketangen, A., K. Jörnsten, and S. Storøy. (1994) “Tabu Search Within a Pivot and Complement Framework.” International Transactions of Operations Research 1, 305–316.
Mulvey, J.M., and H. Vladimirou. (1991). “Applying the Progressive Hedging Algorithm to Stochastic Generalized Networks.” Annals of OR 30, 399–424.
Mulvey, J.M., and H. Vladimirou. (1992). “Stochastic Network Programming for Financial Planning Problems.” Management Science 38, 1642–1664.
Murtagh, B.A., and M.A. Saunders. (1993). “MINOS 5.4 User's Guide.” Technical Report SOL83–20R, SOL, OR, Stanford University, Stanford, CA 94305.
Rockafellar, R.T., and R.J.-B. Wets. (1991). “Scenarios and Policy Aggregation in Optimization Under Uncertainty.” Math. of OR 16, 119–147.
Wallace, S.W., and T. Helgason. (1991). “Structural Properties of the Progresive Hedging Algorithm”. Annals of OR 30, 445–456.
Wets, R.J.-B. (1989). “The Aggregation Principle in Scenario Analysis and Stochastic Optimization.” In S.W. Wallace (Ed.), Algorithms and Model Formulations in Mathematical Programming. Berlin: Springer.
Wets, R.J.-B. (1991). “Decomposition by Stratification for Multistage Stochastic Programs.” Internal Note, IBM Watson Research Center, Yorktown, NY.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Løkketangen, A., Woodruff, D.L. Progressive hedging and tabu search applied to mixed integer (0,1) multistage stochastic programming. J Heuristics 2, 111–128 (1996). https://doi.org/10.1007/BF00247208
Issue Date:
DOI: https://doi.org/10.1007/BF00247208