Skip to main content
SpringerLink
Log in

A branch-reduce-cut algorithm for the global optimization of probabilistically constrained linear programs

  • Published:
Mathematical Programming Submit manuscript

Abstract

We consider probabilistically constrained linear programs with general distributions for the uncertain parameters. These problems involve non-convex feasible sets. We develop a branch-and-bound algorithm that searches for a global optimal solution to this problem by successively partitioning the non-convex feasible region and by using bounds on the objective function to fathom inferior partition elements. This basic algorithm is enhanced by domain reduction and cutting plane strategies to reduce the size of the partition elements and hence tighten bounds. The proposed branch-reduce-cut algorithm exploits the monotonicity properties inherent in the problem, and requires solving linear programming subproblems. We provide convergence proofs for the algorithm. Some illustrative numerical results involving problems with discrete distributions are presented.

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. Beraldi, P., Bruni, M., Conforti, D.: Designing robust emergency medical service via stochastic programming. European Journal of Operational Research 158, 183–193 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  2. Beraldi, P., Ruszczyński, A.: A branch and bound method for stochastic integer problems under probabilistic constraints. Optimization Methods and Software 17, 359–382 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  3. Beraldi, P., Ruszczyński, A.: The probabilistic set covering problem. Operations Research 50, 956–967 (2002)

    Article  MathSciNet  Google Scholar 

  4. Bertsimas, D., Tsitsiklis, J.N.: Introduction to Linear Optimization. Athena Scientific, Belmont, Massachusetts (1997)

  5. Charnes, A., Cooper, W.W.: Chance-constrained programming. Management Science 6, 73–89 (1959)

    MATH  MathSciNet  Google Scholar 

  6. Dentcheva, D., Prékopa, A., Ruszczyński, A.: Concavity and efficient points of discrete distributions in probabilistic programming. Mathematical Programming 89, 55–77 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  7. Dentcheva, D., Prékopa, A., Ruszczyński, A.: On convex probabilistic programming with discrete distributions. Nonlinear Analysis 47, 1997–2009 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  8. Gaivoronski, A., Pflug, G.: Value-at-risk in portfolio optimization: properties and computational approach. The Journal of Risk 7, 1–33 (2005)

    Google Scholar 

  9. Horst, R., Pardalos, P.M., Thoai, N.V.: Introduction to Global Optimization. Kluwer Academic Publishers, Dordrecht (2001)

  10. Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches. Springer-Verlag, Berlin, Germany (1996)

  11. Land, A., Doig, A.: An automatic method for solving discrete programming problems. Econometrica 28, 497–520 (1960)

    Article  MATH  MathSciNet  Google Scholar 

  12. Li, D., Sun, X.L., Biswal, M.P., Gao, F.: Convexification, concavification and monotonization in global optimization. Annals of Operations Research 105, 213–226 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  13. LINDO Systems Inc.: LINDO API 2.0 and LINGO 8.0. http://www.lindo.com/

  14. Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley-Interscience, New York, USA (1999)

  15. Prékopa, A.: Contributions to the theory of stochastic programming. Mathematical Programming 4, 202–221 (1973)

    Article  MATH  MathSciNet  Google Scholar 

  16. Prékopa, A.: Sharp bounds on probabilities using linear programming. Operations Research 38, 227–239 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  17. Prékopa, A.: Stochastic Programming. Kluwer Academic Publishers, Dordrecht, Ther Netherlands (1995)

  18. Ruszczyński, A.: Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra. Mathematical Programming Ser. A93, 195–215 (2002)

    Google Scholar 

  19. Sahinidis, N.V.: BARON: A global optimization software. http://archimedes.scs.uiuc.edu/baron/ baron.html

  20. Sahinidis, N.V.: Optimization under uncertainty: state-of-art and opportunities. Computers & Chemical Engineering 28, 971–983 (2004)

    Article  Google Scholar 

  21. Sen, S.: Relaxations for probabilistically constrained programs with discrete random variables. Operations Research Letters 11, 81–86 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  22. Sen, S., Higle, J.L.: An introductory tutorial on stochastic linear programming models. Interfaces 29 (2), 31–61 (1999)

    Google Scholar 

  23. Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer Academic Publishers, Dordrecht (2002)

  24. Toh, K.A.: Global optimization by monotonic transformation. Computational Optimization and Applications 23, 77–99 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  25. Tuy, H.: Monotonic optimization: Problems and solution approaches. SIAM Journal of Optimization 11 (2), 464–494 (2000)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

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

    Myun-Seok Cheon, Shabbir Ahmed & Faiz Al-Khayyal

Authors
  1. Myun-Seok Cheon
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shabbir Ahmed
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Faiz Al-Khayyal
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Shabbir Ahmed.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Cheon, MS., Ahmed, S. & Al-Khayyal, F. A branch-reduce-cut algorithm for the global optimization of probabilistically constrained linear programs. Math. Program. 108, 617–634 (2006). https://doi.org/10.1007/s10107-006-0725-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-006-0725-5

Keywords

Search

Navigation