Decomposition methods for global solution of mixed-integer linear programs. (English) Zbl 07836043
Summary: This paper introduces two decomposition-based methods for two-block mixed-integer linear programs (MILPs), which aim to take advantage of separable structures of the original problem by solving a sequence of lower-dimensional MILPs. The first method is based on the \(\ell_1\)-augmented Lagrangian method, and the second one is based on a modified alternating direction method of multipliers. In the presence of certain block-angular structures, both methods create parallel subproblems in one block of variables and add nonconvex cuts to update the other block; they converge to globally optimal solutions of the original MILP under proper conditions. Numerical experiments on three classes of MILPs demonstrate the advantages of the proposed methods on structured problems over the state-of-the-art MILP solvers.
MSC:
| 90C11 | Mixed integer programming |
| 90C26 | Nonconvex programming, global optimization |
| 49M27 | Decomposition methods |
Keywords:
mixed integer linear programs; decomposition method; augmented Lagrangian method; alternating direction method of multipliersReferences:
| [1] | Achterberg, T. and Wunderling, R., Mixed integer programming: Analyzing 12 years of progress, in Facets of Combinatorial Optimization, Springer, New York, 2013, pp. 449-481. · Zbl 1317.90206 |
| [2] | Ahmed, S., Cabral, F. G., and da Costa, B. F. P., Stochastic Lipschitz dynamic programming, Math. Program., 191 (2022), pp. 755-793. · Zbl 1489.90072 |
| [3] | Ahmed, S., Tawarmalani, M., and Sahinidis, N. V., A finite branch-and-bound algorithm for two-stage stochastic integer programs, Math. Program., 100 (2004), pp. 355-377. · Zbl 1068.90084 |
| [4] | Alavian, A. and Rotkowitz, M. C., Improving ADMM-based optimization of mixed integer objectives, in Proceedings of the 51st Annual Conference on Information Sciences and Systems (CISS), , IEEE, 2017, pp. 1-6. |
| [5] | Andreani, R., Birgin, E. G., Martínez, J. M., and Schuverdt, M. L., On augmented Lagrangian methods with general lower-level constraints, SIAM J. Optim., 18 (2007), pp. 1286-1309. · Zbl 1151.49027 |
| [6] | Angulo, G., Ahmed, S., and Dey, S. S., Improving the integer L-shaped method, INFORMS J. Comput., 28 (2016), pp. 483-499. · Zbl 1348.90498 |
| [7] | Benders, J. F., Partitioning procedures for solving mixed-variables programming problems, Numer. Math., 4 (1962), pp. 238-252. · Zbl 0109.38302 |
| [8] | Bertsekas, D. P., Constrained Optimization and Lagrange Multiplier Methods, Academic Press, New York, 2014. |
| [9] | Bezanson, J., Edelman, A., Karpinski, S., and Shah, V. B., Julia: A fresh approach to numerical computing, SIAM Rev., 59 (2017), pp. 65-98. · Zbl 1356.68030 |
| [10] | Bixby, R. E., A brief history of linear and mixed-integer programming computation, Doc. Math., 2012 (2012), pp. 107-121. · Zbl 1270.90003 |
| [11] | Blair, C. E. and Jeroslow, R. G., The value function of a mixed integer program: I, Discrete Math., 19 (1977), pp. 121-138. · Zbl 0364.90074 |
| [12] | Bodur, M., Dash, S., Günlük, O., and Luedtke, J., Strengthened benders cuts for stochastic integer programs with continuous recourse, INFORMS J. Comput., 29 (2017), pp. 77-91. · Zbl 1364.90220 |
| [13] | Boland, N., Christiansen, J., Dandurand, B., Eberhard, A., and Oliveira, F., A parallelizable augmented Lagrangian method applied to large-scale non-convex-constrained optimization problems, Math. Program., 175 (2019), pp. 503-536. · Zbl 1431.90116 |
| [14] | Burachik, R. S., Gasimov, R. N., Ismayilova, N. A., and Kaya, C. Y., On a modified subgradient algorithm for dual problems via sharp augmented Lagrangian, J. Global Optim., 34 (2006), pp. 55-78. · Zbl 1098.90091 |
| [15] | Burachik, R. S., Iusem, A. N., and Melo, J. G., A primal dual modified subgradient algorithm with sharp Lagrangian, J. Global Optim., 46 (2010), pp. 347-361. · Zbl 1188.90200 |
| [16] | Burachik, R. S., Iusem, A. N., and Melo, J. G., An inexact modified subgradient algorithm for primal-dual problems via augmented Lagrangians, J. Optim. Theory Appl., 157 (2013), pp. 108-131. · Zbl 1266.90194 |
| [17] | Camisa, A., Notarnicola, I., and Notarstefano, G., A primal decomposition method with suboptimality bounds for distributed mixed-integer linear programming, in Proceedings of the Conference on Decision and Control (CDC), , IEEE, 2018, pp. 3391-3396. |
| [18] | Carøe, C. C. and Schultz, R., Dual decomposition in stochastic integer programming, Oper. Res. Lett., 24 (1999), pp. 37-45. · Zbl 1063.90037 |
| [19] | Carøe, C. C. and Tind, J., L-shaped decomposition of two-stage stochastic programs with integer recourse, Math. Program., 83 (1998), pp. 451-464. · Zbl 0920.90107 |
| [20] | Chen, B., Küçükyavuz, S., and Sen, S., Finite disjunctive programming characterizations for general mixed-integer linear programs, Oper. Res., 59 (2011), pp. 202-210. · Zbl 1218.90132 |
| [21] | Chen, B., Küçükyavuz, S., and Sen, S., A computational study of the cutting plane tree algorithm for general mixed-integer linear programs, Oper. Res. Lett., 40 (2012), pp. 15-19. · Zbl 1242.90123 |
| [22] | Chen, R. and Luedtke, J., On generating Lagrangian cuts for two-stage stochastic integer programs, INFORMS J. Comput., 34 (2022), pp. 2332-2349. · Zbl 07587572 |
| [23] | Cordova, M., de Oliveira, W., and Sagastizábal, C., Revisiting augmented Lagrangian duals, Math. Program., 196 (2022), pp. 235-277. · Zbl 1505.65224 |
| [24] | Dunning, I., Huchette, J., and Lubin, M., JuMP: A modeling language for mathematical optimization, SIAM Rev., 59 (2017), pp. 295-320. · Zbl 1368.90002 |
| [25] | Eckstein, J. and Bertsekas, D. P., On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55 (1992), pp. 293-318. · Zbl 0765.90073 |
| [26] | Feizollahi, M. J., Ahmed, S., and Sun, A., Exact augmented Lagrangian duality for mixed integer linear programming, Math. Program., 161 (2017), pp. 365-387. · Zbl 1364.90226 |
| [27] | Gabay, D., Applications of the method of multipliers to variational inequalities, in Augmented Lagrangian Methods: Applications to the Solution of Boundary Value Problems, Fortin, M. and Glowinski, R., eds., Elsevier, Amsterdam, 1983, pp. 299-331. · Zbl 0525.65045 |
| [28] | Gabay, D. and Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 2 (1976), pp. 17-40. · Zbl 0352.65034 |
| [29] | Gade, D., Küçükyavuz, S., and Sen, S., Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs, Math. Program., 144 (2014), pp. 39-64. · Zbl 1291.90143 |
| [30] | Gasimov, R. N., Augmented Lagrangian duality and nondifferentiable optimization methods in nonconvex programming, J. Global Optim., 24 (2002), pp. 187-203. · Zbl 1047.90048 |
| [31] | Glowinski, R. and Marroco, A., Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de dirichlet non linéaires, Revue française d’automatique, informatique, recherche opérationnelle, Anal. Numer., 9 (1975), pp. 41-76. · Zbl 0368.65053 |
| [32] | Gurobi Optimizer Reference Manual, Gurobi Optimization, version 9.5.2, http://www.gurobi.com, 2022. |
| [33] | Hestenes, M. R., Multiplier and gradient methods, J. Optim. Theory Appl., 4 (1969), pp. 303-320. · Zbl 0174.20705 |
| [34] | Huang, X. and Yang, X., A unified augmented Lagrangian approach to duality and exact penalization, Math. Oper. Res., 28 (2003), pp. 533-552. · Zbl 1082.90135 |
| [35] | Huangfu, Q. and Hall, J. J., Parallelizing the dual revised simplex method, Math. Program. Comput., 10 (2018), pp. 119-142. · Zbl 1402.90084 |
| [36] | Jiang, B., Lin, T., Ma, S., and Zhang, S., Structured nonconvex and nonsmooth optimization: Algorithms and iteration complexity analysis, Comput. Optim. Appl., 72 (2019), pp. 115-157. · Zbl 1411.90274 |
| [37] | Kall, P., Wallace, S. W., and Kall, P., Stochastic Programming, Vol. 6, Springer, New York, 1994. · Zbl 0812.90122 |
| [38] | Kanno, Y. and Fujita, S., Alternating direction method of multipliers for truss topology optimization with limited number of nodes: A cardinality-constrained second-order cone programming approach, Optim. Eng., 19 (2018), pp. 327-358. · Zbl 1397.74163 |
| [39] | Kanno, Y. and Kitayama, S., Alternating direction method of multipliers as a simple effective heuristic for mixed-integer nonlinear optimization, Struct. Multidiscip. Optim., 58 (2018), pp. 1291-1295. |
| [40] | Laporte, G. and Louveaux, F. V., The integer L-shaped method for stochastic integer programs with complete recourse, Oper. Res. Lett., 13 (1993), pp. 133-142. · Zbl 0793.90043 |
| [41] | Li, C. and Grossmann, I. E., An improved L-shaped method for two-stage convex 0-1 mixed integer nonlinear stochastic programs, Comput. Chem. Eng., 112 (2018), pp. 165-179. |
| [42] | Li, C. and Grossmann, I. E., A generalized benders decomposition-based branch and cut algorithm for two-stage stochastic programs with nonconvex constraints and mixed-binary first and second stage variables, J. Global Optim., 75 (2019), pp. 247-272. · Zbl 1428.90106 |
| [43] | Malherbe, C. and Vayatis, N., Global optimization of Lipschitz functions, in Proceedings of the International Conference on Machine Learning, , PMLR, 2017, pp. 2314-2323. |
| [44] | Mayne, D. Q. and Polak, E., Outer approximation algorithm for nondifferentiable optimization problems, J. Optim. Theory Appl., 42 (1984), pp. 19-30. · Zbl 0505.90068 |
| [45] | Melo, J. G. and Monteiro, R. D., Iteration-Complexity of a Linearized Proximal Multiblock ADMM Class for Linearly Constrained Nonconvex Optimization Problems, 2017, http://www.optimization-online.org/DB_HTML/2017/04/5964.html. |
| [46] | Monteiro, R. D. C. and Svaiter, B. F., Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers, SIAM J. Optim., 23 (2013), pp. 475-507. · Zbl 1267.90181 |
| [47] | Ntaimo, L., Fenchel decomposition for stochastic mixed-integer programming, J. Global Optim., 55 (2013), pp. 141-163. · Zbl 1262.90117 |
| [48] | Ntaimo, L. and Sen, S., The million-variable “march” for stochastic combinatorial optimization, J. Global Optim., 32 (2005), pp. 385-400. · Zbl 1098.90045 |
| [49] | Powell, M. J., A method for nonlinear constraints in minimization problems, in Optimization, Fletcher, R., ed., Academic Press, New York, 1969, pp. 283-298. · Zbl 0194.47701 |
| [50] | Qi, Y. and Sen, S., The ancestral benders cutting plane algorithm with multi-term disjunctions for mixed-integer recourse decisions in stochastic programming, Math. Program., 161 (2017), pp. 193-235. · Zbl 1356.90098 |
| [51] | Rahmaniani, R., Ahmed, S., Crainic, T. G., Gendreau, M., and Rei, W., The Benders dual decomposition method, Oper. Res., 68 (2020), pp. 878-895. · Zbl 1456.90108 |
| [52] | Rahmaniani, R., Crainic, T. G., Gendreau, M., and Rei, W., The Benders decomposition algorithm: A literature review, European J. Oper. Res., 259 (2017), pp. 801-817. · Zbl 1402.90158 |
| [53] | Rockafellar, R. T., The multiplier method of Hestenes and Powell applied to convex programming, J. Optim. Theory Appl., 12 (1973), pp. 555-562. · Zbl 0254.90045 |
| [54] | Rockafellar, R. T., Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res., 1 (1976), pp. 97-116. · Zbl 0402.90076 |
| [55] | Rockafellar, R. T. and Wets, R. J.-B., Variational Analysis, , Springer, Berlin, 2009. |
| [56] | Ruszczynski, A., Nonlinear Optimization, Princeton University Press, Princeton, NJ, 2011. |
| [57] | Schultz, R., Stougie, L., and Van Der Vlerk, M. H., Solving stochastic programs with integer recourse by enumeration: A framework using Gröbner basis, Math. Program., 83 (1998), pp. 229-252. · Zbl 0920.90114 |
| [58] | Sen, S. and Higle, J. L., The \(C^3\) theorem and a \(D^2\) algorithm for large scale stochastic mixed-integer programming: Set convexification, Math. Program., 104 (2005), pp. 1-20. · Zbl 1159.90464 |
| [59] | Sen, S. and Sherali, H. D., Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming, Math. Program., 106 (2006), pp. 203-223. · Zbl 1134.90449 |
| [60] | Sherali, H. D. and Fraticelli, B. M., A modification of Benders’ decomposition algorithm for discrete subproblems: An approach for stochastic programs with integer recourse, J. Global Optim., 22 (2002), pp. 319-342. · Zbl 1045.90040 |
| [61] | Shi, W., Ling, Q., Yuan, K., Wu, G., and Yin, W., On the linear convergence of the ADMM in decentralized consensus optimization, IEEE Trans. Signal Process., 62 (2014), pp. 1750-1761. · Zbl 1394.94532 |
| [62] | Sun, K. and Sun, X. A., A two-level distributed algorithm for nonconvex constrained optimization, Comput. Optim. Appl., 84 (2023), pp. 609-649. · Zbl 1516.90067 |
| [63] | Takapoui, R., The Alternating Direction Method of Multipliers for Mixed-Integer Optimization Applications, Ph.D. thesis, Stanford University, 2017. |
| [64] | Takapoui, R., Moehle, N., Boyd, S., and Bemporad, A., A simple effective heuristic for embedded mixed-integer quadratic programming, Internat. J. Control, 93 (2020), pp. 2-12. · Zbl 1434.90117 |
| [65] | van der Laan, N. and Romeijnders, W., A converging Benders’ decomposition algorithm for two-stage mixed-integer recourse models, Oper. Res., to appear. |
| [66] | Van Slyke, R. M. and Wets, R., L-shaped linear programs with applications to optimal control and stochastic programming, SIAM J. Appl. Math., 17 (1969), pp. 638-663. · Zbl 0197.45602 |
| [67] | Wang, Y., Yin, W., and Zeng, J., Global convergence of ADMM in nonconvex nonsmooth optimization, J. Sci. Comput., 78 (2019), pp. 29-63. · Zbl 1462.65072 |
| [68] | Wu, B. and Ghanem, B., \( \ell_p\)-box ADMM: A versatile framework for integer programming, IEEE Trans. Pattern Anal. Mach. Intell., 41 (2018), pp. 1695-1708. |
| [69] | Xu, Y. and Yin, W., A globally convergent algorithm for nonconvex optimization based on block coordinate update, J. Sci. Comput., 72 (2017), pp. 700-734. · Zbl 1378.65126 |
| [70] | Yadav, A. K., Ranjan, R., Mahbub, U., and Rotkowitz, M. C., New methods for handling binary constraints, in Proceedings of the 54th Annual Allerton Conference on Communication, Control, and Computing, , IEEE, 2016, pp. 1074-1080. |
| [71] | Yao, Y., Zhu, X., Dong, H., Wu, S., Wu, H., Tong, L. C., and Zhou, X., ADMM-based problem decomposition scheme for vehicle routing problem with time windows, Transport. Res. B Methodol., 129 (2019), pp. 156-174. |
| [72] | Zhang, S. and Sun, X. A., Stochastic dual dynamic programming for multistage stochastic mixed-integer nonlinear optimization, Math. Program., 196 (2022), pp. 935-985. · Zbl 1506.90185 |
| [73] | Zou, J., Ahmed, S., and Sun, X. A., Stochastic dual dynamic integer programming, Math. Program., 175 (2019), pp. 461-502. · Zbl 1412.90101 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
