Solving stochastic programs with integer recourse by enumeration: A framework using Gröbner basis | Mathematical Programming Skip to main content
Springer Nature Link
Log in

Solving stochastic programs with integer recourse by enumeration: A framework using Gröbner basis

  • Published:
Mathematical Programming Submit manuscript

Abstract

In this paper we present a framework for solving stochastic programs with complete integer recourse and discretely distributed right-hand side vector, using Gröbner basis methods from computational algebra to solve the numerous second-stage integer programs. Using structural properties of the expected integer recourse function, we prove that under mild conditions an optimal solution is contained in a finite set. Furthermore, we present a basic scheme to enumerate this set and suggest improvements to reduce the number of function evaluations needed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. B. Bank, R. Mandel, Parametric Integer Optimization, Akademie Verlag, Berlin, 1988.

    MATH  Google Scholar 

  2. C.E. Blair, R.G. Jeroslow, The value function of a mixed integer program: I, Discrete Mathematics 19 (1977) 121–138.

    Article  MATH  MathSciNet  Google Scholar 

  3. B. Buchberger, Gröbner bases: An algorithmic method in polynomial ideal theory, in: N.K. Bose (Ed.), Multidimensional Systems Theory, vol. 6, Reidel, Dordrecht, 1985.

    Google Scholar 

  4. A. Capani, G. Niesi, CoCoa User's Manual, Department of Mathematics, University of Genova, release 3.0b edn., 1995.

  5. C.C. Caröe, J. Tind, L-shaped decomposition of two-stage stochastic programs with integer recourse, Technical Report, Institute of Mathematics, University of Copenhagen, 1995.

  6. T. Christof, PORTA—A polyhedron representation transformation algorithm, Available via http:// www.iwr.uni-heidelberg.de/iwr/comopt/soft/PORTA/readme.html.

  7. P. Conti, C. Traverso, Buchberger algorithm and integer programming, in: Proceedings of AAECC-9 (New Orleans), Lecture Notes in Computer Science, vol. 539, Springer, Berlin, 1991, pp. 130–139.

    Google Scholar 

  8. D. Cox, J. Little, D. O'Shea, Ideals, Varieties and Algorithms, Springer, New York, 1992.

    MATH  Google Scholar 

  9. Using the CPLEX Callable Library, CPLEX Optimization, 1995.

  10. Y.M. Ermoliev, V.I. Norkin, R.J.-B. Wets, The minimization of semicontinuous functions: Mollifier subgradients, SIAM Journal on Control and Optimization 33 (1) (1995) 149–167.

    Article  MATH  MathSciNet  Google Scholar 

  11. Yu. Ermoliev, R.J.-B. Wets, Numerical Techniques for Stochastic Optimization, Springer, Berlin, 1988.

    MATH  Google Scholar 

  12. J.L. Higle, S. Sen, Stochastic decomposition: An algorithm for two-stage linear programs with recourse, Mathematics of Operations Research 16 (1991) 650–669.

    Article  MATH  MathSciNet  Google Scholar 

  13. S. Hosten, B. Sturmfels, GRIN: An implementation of Gröbner bases for integer programming, in: Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 920, Springer, Berlin, 1995, pp. 267–276.

    Google Scholar 

  14. P. Kall, S. W. Wallace, Stochastic Programming, Wiley, Chichester, 1994.

    MATH  Google Scholar 

  15. W.K. Klein Haneveld, L. Stougie, M. H. van der Vlerk, An algorithm for the construction of convex hulls in simple integer recourse programming, Annals of Operations Research 64 (1996) 67–81.

    Article  MATH  MathSciNet  Google Scholar 

  16. W.K. Klein Haneveld, M.H. van der Vlerk, On the expected value function of a simple integer recourse problem with random technology matrix, Journal of Computational and Applied Mathematics 56 (1994) 45–53.

    Article  MATH  MathSciNet  Google Scholar 

  17. B.J. Lageweg, J.K. Lenstra, A.H.G. Rinnooy Kan, L. Stougie, Stochastic integer programming by dynamic programming, in: Yu. Ermoliev, R.J.-B. Wets (eds.), Numerical Techniques for Stochastic Optimization, ch. 21, Springer, Berlin, 1988.

    Google Scholar 

  18. G. Laporte, F.V. Louveaux, The integer L-shaped method for stochastic integer programs with complete recourse, Operations Research Letters 13 (1993) 133–142.

    Article  MATH  MathSciNet  Google Scholar 

  19. F.V. Louveaux, M.H. van der Vlerk, Stochastic programming with simple integer recourse, Mathematical Programming 61 (1993) 301–325.

    Article  MathSciNet  Google Scholar 

  20. G.L. Nemhauser, L.A. Wolsey, Integer and Combinational Optimization, Wiley, New York, 1988.

    Google Scholar 

  21. A. Prékopa, Stochastic Programming, Kluwer Academic Publishers, Dordrecht, 1995.

    Google Scholar 

  22. R.T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, 1970.

    MATH  Google Scholar 

  23. A. Ruszczyński, A regularized decomposition method for minimizing a sum of polyhedral functions, Mathematical Programming 35 (1986) 309–333.

    Article  MathSciNet  MATH  Google Scholar 

  24. A. Ruszczyński, Y. Ermoliev, V. Norkin, On optimal allocation of indivisibles under uncertainty, Operations Research, to appear.

  25. R. Schultz, Continuity properties of expectation functions in stochastic integer programming, Mathematics of Operations Research 18 (1993) 578–589.

    Article  MATH  MathSciNet  Google Scholar 

  26. R. Schultz, On structure and stability in stochastic programs with random technology matrix and complete integer recourse, Mathematical Programming 70 (1995) 73–89.

    MathSciNet  Google Scholar 

  27. R. Schultz, L. Stougie, M.H. van der Vlerk, Two-stag stochastic integer programming: A survey, Statistica Neerlandica 50 (3) (1996) 404–416.

    Article  MATH  MathSciNet  Google Scholar 

  28. L. Stougie, M.H. van der Vlerk, Stochastic integer programming, in: M. Dell'Amico, F. Maffioli, S. Martello (Eds.), Annotated Bibliographies in Combinatorial Optimization, ch. 9 Wiley, 1997, pp. 127–141.

  29. S.R. Tayur, A new algorithm to solve stochastic integer programs with application to plant management, Technical report, Carnegie Mellon University, Pittsburgh, PA, in preparation.

  30. S.R. Tayur, R.R. Thomas, N.R. Natraj, An algebraic geometry algorithm for scheduling in the presence of setups and correlated demands, Mathematical Programming 69 (1995) 369–401.

    MathSciNet  Google Scholar 

  31. R.R. Thomas, A geometric Buchberger algorithm for integer programming, Mathematics of Operations Research 20 (1995) 864–884.

    Article  MATH  MathSciNet  Google Scholar 

  32. R.R. Thomas, R. Weismantel, Truncated Gröbner bases for integer programming, Applicable Algebra in Engineering Communication and Computing 8 (1997) 241–256.

    Article  MATH  MathSciNet  Google Scholar 

  33. R. Urbaniak, R. Weismantel, G. Ziegler, A variant of Buchberger's algorithm for integer programming, SIAM Journal on Discrete Mathematics 10 (1997) 96–108.

    Article  MATH  MathSciNet  Google Scholar 

  34. M.H. van der Vlerk, Stochastic programming with integer recourse, Ph.D. Thesis, University of Groningen, The Netherlands, 1995.

    Google Scholar 

  35. R. Van Slyke, R.J.-B. Wets, L-shaped linear programs with applications to control and stochastic programming, SIAM Journal on Applied Mathematics 17 (1963) 638–663.

    Article  Google Scholar 

  36. S.W. Wallace, R.J.-B. Wets, Preprocessing in stochastic programming: The case of linear programs, ORSA Journal on Computing 4 (1992) 45–59.

    MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Mathematical Institute, University of Leipzig, Augustusplatz 10/11, D-04109, Leipzig, Germany

    Rüdiger Schultz

  2. Department of Mathematics and Computing Science, Eindhoven University of Technology, P.O. Box 513, NL-5600 MB, Eindhoven, The Netherlands

    Leen Stougie

  3. Department of Econometrics, University of Groningen, P.O. Box 800, NL-9700 AV, Groningen, The Netherlands

    Maarten H. van der Vlerk

Authors
  1. Rüdiger Schultz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Leen Stougie
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Maarten H. van der Vlerk
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Schultz, R., Stougie, L. & van der Vlerk, M.H. Solving stochastic programs with integer recourse by enumeration: A framework using Gröbner basis. Mathematical Programming 83, 229–252 (1998). https://doi.org/10.1007/BF02680560

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02680560

Keywords

Search

Navigation