Skip to main content
SpringerLink
Log in

Inexact stabilized Benders’ decomposition approaches with application to chance-constrained problems with finite support

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

We explore modifications of the standard cutting-plane approach for minimizing a convex nondifferentiable function, given by an oracle, over a combinatorial set, which is the basis of the celebrated (generalized) Benders’ decomposition approach. Specifically, we combine stabilization—in two ways: via a trust region in the \(L_1\) norm, or via a level constraint—and inexact function computation (solution of the subproblems). Managing both features simultaneously requires a nontrivial convergence analysis; we provide it under very weak assumptions on the handling of the two parameters (target and accuracy) controlling the informative on-demand inexact oracle corresponding to the subproblem, strengthening earlier know results. This yields new versions of Benders’ decomposition, whose numerical performance are assessed on a class of hybrid robust and chance-constrained problems that involve a random variable with an underlying discrete distribution, are convex in the decision variable, but have neither separable nor linear probabilistic constraints. The numerical results show that the approach has potential, especially for instances that are difficult to solve with standard techniques.

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. Baena, D., Castro, J., Frangioni, A.: Stabilized Benders methods for large-scale combinatorial optimization: applications to data privacy (2015)

  2. Bao, X., Sahinidis, N., Tawarmalani, M.: Multiterm polyhedral relaxations for nonconvex, quadratically-constrained quadratic programs. Optim. Methods Softw. 24, 485–504 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  3. Ben Amor, H., Desrosiers, J., Frangioni, A.: On the choice of explicit stabilizing terms in column generation. Discret. Appl. Math. 157(6), 1167–1184 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  4. Ben-Tal, A., Ghaoui, L.E., Nemirovski, A.: Robust Optimization. Princeton University Press, Princeton (2009)

    Book  MATH  Google Scholar 

  5. Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization: Analysis, Algorithms, Engineering Applications. MPS-SIAM Series on Optimization. SIAM, Philadelphia (2001)

    Book  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  7. Boyd, S., Vandenberghe, L.: Convex optimization. http://www.stanford.edu/~boyd/cvxbook ISBN 0 521 83378 7 (2006)

  8. Calafiore, G.C., Campi, M.C.: Uncertain convex programs: randomized solutions and confidence levels. Math.l Program. 102(1), 25–46 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  9. Caroe, C.C., Tind, J.: L-shaped decomposition of two-stage stochastic programs with integer recourse. Math. Program. 83, 451–464 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  10. Codato, G., Fischetti, M.: Combinatorial benders’ cuts for mixed-integer linear programming. Oper. Res. 54(4), 756–766 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  11. Costa, A.M.: A survey on benders decomposition applied to fixed-charge network design problems. Comput. Oper. Res. 32(6), 1429–1450 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  12. d’Ambrosio, C., Frangioni, A., Liberti, L., Lodi, A.: On interval-subgradient cuts and no-good cuts. Oper. Res. Lett. 38, 341–345 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  13. d’Antonio, G., Frangioni, A.: Convergence analysis of deflected conditional approximate subgradient methods. SIAM J. Optim. 20(1), 357–386 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  14. de Klerk, E.: The complexity of optimizing over a simplex, hypercube or sphere: a short survey. Central Eur. J. Oper. Res. 16(2), 111–125 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  15. de Oliveira, W.: Regularized nonsmooth optimization methods for convex minlp problems. TOP pp. 1–28 (2016). doi:10.1007/s11750-016-0413-4

  16. de Oliveira, W., Sagastizábal, C.: Level bundle methods for oracles with on demand accuracy. Optim. Methods Softw. 29(6), 1180–1209 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  17. de Oliveira, W., Sagastizábal, C., Lemaréchal, C.: Convex proximal bundle methods in depth: a unified analysis for inexact oracles. Math. Prog. Ser. B 148, 241–277 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  18. Dentcheva, D.: Optimization models with probabilistic constraints. In: Calafiore, G., Dabbene, F. (eds.) Probabilistic and Randomized Methods for Design Under Uncertainty, 1st edn, pp. 49–97. Springer, Newe York (2006)

    Chapter  Google Scholar 

  19. Dentcheva, D.: Optimisation models with probabilistic constraints. In: Shapiro, A., Dentcheva, D., Ruszczyński, A. (eds.) Lectures on Stochastic Programming. Modeling and Theory, MPS-SIAM series on optimization, vol. 9, pp. 87–154. SIAM and MPS, Philadelphia (2009)

  20. Dentcheva, D., Lai, B., Ruszczyński, A.: Dual methods for probabilistic optimization problems. Math. Methods Oper. Res. 60(2), 331–346 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  21. Dentcheva, D., Martinez, G.: Regularization methods for optimization problems with probabilistic constraints. Math. Program. (Ser. A) 138(1–2), 223–251 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  22. Dentcheva, D., Prékopa, A., Ruszczyński, A.: Concavity and efficient points for discrete distributions in stochastic programming. Math. Program. 89, 55–77 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  23. Dinter, J.V., Rebenack, S., Kallrath, J., Denholm, P., Newman, A.: The unit commitment model with concave emissions costs: a hybrid benders’ decomposition with nonconvex master problems. Ann. Oper. Res. 210(1), 361–386 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  24. Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002). doi:10.1007/s101070100263

    Article  MathSciNet  MATH  Google Scholar 

  25. Fábián, C.: Bundle-type methods for inexact data. In: Csendes, T., Rapcsk, T. (eds.), Proceedings of the XXIV Hungarian Operations Researc Conference (Veszprém, 1999), vol. 8 (pecial issue), pp. 35–55 (2000)

  26. Fábián, C., Wolf, C., Koberstein, A., Suhl, L.: Risk-averse optimization in two-stage stochastic models: computational aspects and a study. SIAM J. Optim. 25(1), 28–52 (2015)

    Article  MathSciNet  Google Scholar 

  27. Feltenmark, S., Kiwiel, K.: Dual applications of proximal bundle methods, including lagrangian relaxation of nonconvex problems. SIAM J. Optim. 10(3), 697–721 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  28. Fischetti, M., Lodi, A.: Local branching. Math. Program. 98(1–3), 23–47 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  29. Fischetti, M., Salvagnin, D., Zanette, A.: A note on the selection of Benders cuts. Math. Program. 124(1), 175–182 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  30. Floudas, C.A.: Generalized benders decomposition. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, 2nd edn, pp. 1163–1174. Springer, New York (2009)

    Chapter  Google Scholar 

  31. Frangioni, A.: Generalized Bundle methods. SIAM J. Optim. 13(1), 117–156 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  32. Frangioni, A., Gendron, B.: A stabilized structured dantzig-wolfe decomposition method. Math. Program. B 104(1), 45–76 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  33. Frangioni, A., Gorgone, E.: Generalized bundle methods for sum-functions with “easy” components: Applications to multicommodity network design. Math. Program. 145(1), 133–161 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  34. Frangioni, A., Lodi, A., Rinaldi, G.: New approaches for optimizing over the semimetric polytope. Math. Program. 104(2–3), 375–388 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  35. Geoffrion, A.M.: Generalized benders decomposition. J. Optim. Theory Appl. 10(4), 237–260 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  36. Hiriart-Urruty, J., Lemaréchal, C.: Convex Analysis and Minimization Algorithms II, 2nd edn. No. 306 in Grundlehren der mathematischen Wissenschaften. Springer, Berlin (1996)

  37. Hooker, J.N., Ottosson, G.: Logic-based benders decomposition. Math. Program. 96, 33–60 (2003)

    MathSciNet  MATH  Google Scholar 

  38. Kelley, J.: The cutting-plane method for solving convex programs. J. Soc. Ind. Appl. Math. 8(4), 703–712 (1960)

    Article  MathSciNet  MATH  Google Scholar 

  39. Kolokolov, A., Kosarev, N.: Analysis of decomposition algorithms with benders cuts for \(p\)-median problem. J. Math. Model. Algorithms 5(2), 189–199 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  40. Lemaréchal, C., Nemirovskii, A., Nesterov, Y.: New variants of bundle methods. Math. Program. 69(1), 111–147 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  41. Li, X., Chen, Y., Barton, P.I.: Nonconvex generalized benders decomposition with piecewise convex relaxations for global optimization of integrated process design and operation problems. Ind. Eng. Chem. Res. 51(21), 7287–7299 (2012)

    Article  Google Scholar 

  42. Liu, X., Küçükyavuz, S., Luedtke, J.: Decomposition algorithm for two-stage chance constrained programs. In: Mathematical Programming Series B, pp. 1–25 (2014). doi:10.1007/s10107-014-0832-7

  43. Luedtke, J.: A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support. Math. Program. 146(1–2), 219–244 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  44. Luedtke, J., Ahmed, S.: A sample approximation approach for optimization with probabilistic constraints. SIAM J. Optim. 19, 674–699 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  45. Marsten, R., Hogan, W., Blankenship, J.: The BOXSTEP method for large-scale optimization. Oper. Res. 23(3), 389–405 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  46. Oliveira, F., Grossmann, I., Hamacher, S.: Accelerating Benders stochastic decomposition for the optimization under uncertainty of the petroleum product supply chain. Comput. Oper. Res. 49(1), 47–58 (2014)

    Article  MathSciNet  Google Scholar 

  47. Prékopa, A.: Dual method for a one-stage stochastic programming problem with random rhs obeying a discrete probabiltiy distribution. Z. Oper. Res. 34, 441–461 (1990)

    MathSciNet  MATH  Google Scholar 

  48. Prékopa, A.: Probabilistic programming. In: Ruszczyński, A., Shapiro, A. (eds.) Stochastic Programming, Handbooks in Operations Research and Management Science, vol. 10, pp. 267–351. Elsevier, Amsterdam (2003)

    Google Scholar 

  49. Prékopa, A., Vízvári, B., Badics, T.: Programming under probabilistic constraints with discrete random variable. In:Giannessi, F., Komlósi, S., Rapcsák, T.(eds.) New Trends in Mathematical Programming : Hommage to Steven Vajda, Applied Optimization, vol. 13, pp. 235–255. Springer, New York (1998)

  50. Ruszczyński, A.: Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra. Math. Program. 93, 195–215 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  51. Ruszczyński, A.: Decomposition methods. In: Ruszczyński, A., Shapiro, A. (eds.) Stochastic Programming, Handbooks in Operations Research and Management Science, vol. 10, pp. 141–211. Elsevier, Amsterdam (2003)

    Google Scholar 

  52. Sahiridis, G.K.D., Minoux, M., Ierapetritou, M.G.: Accelerating benders method using covering cut bundle generation. Int. Trans. Oper. Res. 17, 221–237 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  53. Santoso, T., Ahmed, S., Goetschalcks, M., Shapiro, A.: A stochastic programming approach for supply chain network design under uncertainty. Eur. J. Oper. Res. 167(1), 96–115 (2005)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  55. Shapiro, A., Dentcheva, D., Ruszczyński, A.: Lectures on Stochastic Programming. Modeling and Theory, MPS-SIAM series on optimization, vol. 9. SIAM and MPS, Philadelphia (2009)

  56. Sherali, H., Lunday, B.J.: On generating maximal nondominated Benders cuts. Ann. Oper. Res. 210(1), 57–72 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  57. Tahanan, M., van Ackooij, W., Frangioni, A., Lacalandra, F.: Large-scale unit commitment under uncertainty: a literature survey. 4OR 13(2), 115–171 (2015). doi:10.1007/s10288-014-0279-y

  58. Tran-Dinh, Q., Necoara, I., Diehl, M.: Fast inexact decomposition algorithms for large-scale separable convex optimization. Optimization (to appear) 1–33 (2015). doi:10.1080/02331934.2015.1044898

  59. van Ackooij, W., de Oliveira, W.: Level bundle methods for constrained convex optimization with various oracles. Comput. Optim. Appl. 57(3), 555–597 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  60. van Ackooij, W., Henrion, R.: Gradient formulae for nonlinear probabilistic constraints with Gaussian and Gaussian-like distributions. SIAM J. Optim. 24(4), 1864–1889 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  61. van Ackooij, W., Malick, J.: Decomposition algorithm for large-scale two-stage unit-commitment. Ann. Oper. Res. 238(1), 587–613 (2016). doi:10.1007/s10479-015-2029-8

    Article  MathSciNet  MATH  Google Scholar 

  62. van Ackooij, W., Sagastizábal, C.: Constrained bundle methods for upper inexact oracles with application to joint chance constrained energy problems. SIAM J. Optim. 24(2), 733–765 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  63. van Ackooij, W., Henrion, R., Möller, A., Zorgati, R.: Joint chance constrained programming for hydro reservoir management. Optim. Eng. 15, 509–531 (2014)

    MathSciNet  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  65. Wentges, P.: Accelerating benders’ decomposition for the capacitated facility location problem. Math. Methods Oper. Res. 44(2), 267–290 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  66. Westerlund, T., Pörn, R.: Solving pseudo-convex mixed integer optimization problems by cutting plane techniques. Optim. Eng. 3, 253–280 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  67. Wolf, C., Fábián, C.I., Koberstein, A., Stuhl, L.: Applying oracles of on-demand accuracy in two-stage stochastic programming a computational study. Eur. J. Oper. Res. 239(2), 437–448 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  68. Yang, Y., Lee, J.M.: A tighter cut generation strategy for acceleration of benders decomposition. Comput. Chem. Eng. 44, 84–93 (2012)

    Article  Google Scholar 

  69. Zakeri, G., Philpott, A., Ryan, D.M.: Inexact cuts in benders decomposition. SIAM J. Optim. 10(3), 643–657 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  70. Zaourar, S., Malick, J.: Quadratic stabilization of benders decomposition pp. 1–22 (2014). Draft submitted; Privately communicated

  71. Zappe, C.J., Cabot, A.V.: The application of generalized benders decomposition to certain nonconcave programs. Computers Math. Applic. 21(6/7), 181–190 (1991)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The authors gratefully acknowledge financial support from the Gaspard-Monge program for Optimization and Operations Research (PGMO) project “Consistent Dual Signals and Optimal Primal Solutions”. The first and second authors would also like to acknowledge networking support by the COST Action TD1207.

Author information

Authors and Affiliations

  1. EDF R&D, OSIRIS, 7, Boulevard Gaspard Monge, 91120, Palaiseau Cedex, France

    W. van Ackooij

  2. Dipartimento di Informatica, Università di Pisa, Largo B. Pontecorvo 3, 56127, Pisa, Italy

    A. Frangioni

  3. Universidade do Estado do Rio de Janeiro - UERJ, Rua São Francisco Xavier 524, 20550-900, Rio de Janeiro, Brazil

    W. de Oliveira

Authors
  1. W. van Ackooij
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. Frangioni
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. W. de Oliveira
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to W. van Ackooij.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

van Ackooij, W., Frangioni, A. & de Oliveira, W. Inexact stabilized Benders’ decomposition approaches with application to chance-constrained problems with finite support. Comput Optim Appl 65, 637–669 (2016). https://doi.org/10.1007/s10589-016-9851-z

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-016-9851-z

Keywords

Mathematics Subject Classification

Search

Navigation