Skip to main content
SpringerLink
Log in

Totally unimodular stochastic programs

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

We consider totally unimodular (TU) stochastic programs, that is, two-stage stochastic programs whose extensive-form constraint matrix is TU. We generalize the notion of total unimodularity to apply to sets of matrices and provide properties of such sets. We provide several sufficient conditions on stochastic programs to be TU. When solving TU stochastic problems using the L-shaped method, it is not clear whether the integrality restrictions should be imposed on the master problem. Such restrictions will make each master problem more difficult to solve. On the other hand, solving the linear relaxation of the master typically means sending fractional (and unlikely optimal) solutions to the subproblems, perhaps leading to more iterations. Our computational results investigate this trade-off and provide insight into which strategy is preferable.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ahmed S., Tawarmalani M., Sahinidis N.V.: A finite branch-and-bound algorithm for two-stage stochastic integer programs. Math. Program. 100(2), 355–377 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  2. Benders J.F.: Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4(1), 238–252 (1962)

    Article  MathSciNet  MATH  Google Scholar 

  3. Birge J.R., Louveaux F.V.: Introduction to Stochastic Programming. Springer, New York (1997)

    MATH  Google Scholar 

  4. Dhamdhere, K., Ravi, R., Singh, M.: On stochastic minimum spanning trees. In: Proceedings of the 11th International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 321–334 (2005)

  5. Ghouila-Houri A.: Caracterisation des matrices totalement unimodulaires. C. R. Acad. Sci. Paris 254, 1192–1194 (1962)

    MathSciNet  MATH  Google Scholar 

  6. Hoffman A.J., Kruskal J.B.: Integral boundary points of convex polyhedra. In: Kuhn, H.W., Tucker, A.W. (eds) Linear Inequalities and Related Systems, pp. 223–246. Princeton University Press, Princeton (1956)

    Google Scholar 

  7. Klein Haneveld W.K., van der Vlerk M.H.: Stochastic integer programming: general models and algorithms. Ann. Oper. Res. 85, 39–57 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  8. Kong N., Schaefer A.J.: A factor \({\frac{1}{2}}\) approximation algorithm for two-stage stochastic matching problems. Eur. J. Oper. Res. 172(3), 740–746 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  9. Kong N., Schaefer A.J., Hunsaker B.: Two-stage integer programs with stochastic right-hand sides: a superadditive dual approach. Math. Program. 108(2), 275–296 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  10. Louveaux F.V., van der Vlerk M.: Stochastic programming with simple integer recourse. Math. Program. 61(3), 301–325 (1993)

    Article  MATH  Google Scholar 

  11. Nemhauser G.L., Wolsey L.A.: Integer and Combinatorial Optimization. Wiley, Hoboken (1988)

    MATH  Google Scholar 

  12. Ntaimo L.: Disjunctive decomposition for two-stage stochastic mixed-binary programs with random recourse. Oper. Res. 58(1), 229–243 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  13. Padberg, M.W.: Characterizations of totally unimodular, balanced and perfect matrices. In: Roy, B. (ed.) Combinatorial Programming: Methods and Applications, pp. 275–284. Reidel (1975)

  14. Schrijver A.: Theory of Linear and Integer Programming. Wiley, Hoboken (1986)

    MATH  Google Scholar 

  15. Schultz R.: Stochastic programming with integer variables. Math. Program. 97(1–2), 285–309 (2003)

    MathSciNet  MATH  Google Scholar 

  16. Sen S., Higle J.L.: The C 3 theorem and a D 2 algorithm for large scale stochastic integer programming: Set convexification. Math. Program. 104(1), 1–20 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  17. Sen S., Sherali H.D.: Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming. Math. Program. 106(2), 203–223 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  18. Shmoys D.B., Swamy C.: An approximation scheme for stochastic linear programming and its application to stochastic integer programs. J. ACM 53(6), 978–1012 (2006)

    Article  MathSciNet  Google Scholar 

  19. Stougie, L.: Design and analysis of methods for stochastic integer programming. Ph.D. thesis, University of Amsterdam (1987)

  20. Stougie, L., van der Vlerk, M.H.: Approximation in stochastic integer programming. Technical Report 03A14, University of Groningen, Research Institute SOM (2003)

  21. van der Vlerk M.H.: Convex approximations for complete integer recourse models. Math. Program. 99(2), 297–310 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  22. Van Slyke R., Wets R.J.B.: L-shaped linear programs with applications to optimal control and stochastic programming. SIAM J. Appl. Math. 17(4), 638–663 (1969)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Weldon School of Biomedical Engineering, Purdue University, 206 S. Martin Jischke Dr., West Lafayette, IN, 47907, USA

    Nan Kong

  2. Department of Industrial Engineering, University of Pittsburgh, 1048 Benedum Hall, Pittsburgh, PA, 15261, USA

    Andrew J. Schaefer

  3. School of Industrial and Systems Engineering, Georgia Institute of Technology, 765 Ferst Drive, Atlanta, GA, 30332, USA

    Shabbir Ahmed

Authors
  1. Nan Kong
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andrew J. Schaefer
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shabbir Ahmed
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andrew J. Schaefer.

Additional information

Nan Kong was supported by Air Force Office of Scientific Research grant FA9550-08-1-0268.

Andrew J. Schaefer was supported in part by National Science Foundation awards DMI-0355433, CMMI-0620780, and CMMI-0826141. Shabbir Ahmed was supported in part by National Science Foundation awards DMI-0522485 and DMI-0133943.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kong, N., Schaefer, A.J. & Ahmed, S. Totally unimodular stochastic programs. Math. Program. 138, 1–13 (2013). https://doi.org/10.1007/s10107-012-0529-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-012-0529-8

Keywords

Mathematics Subject Classification

Search

Navigation