×

zbMATH — the first resource for mathematics

Multi-tree decomposition methods for large-scale mixed integer nonlinear optimization. (English) Zbl 1446.90109
Velásquez-Bermúdez, Jesús M. (ed.) et al., Large scale optimization in supply chains and smart manufacturing. Theory and applications. Cham: Springer. Springer Optim. Appl. 149, 27-58 (2019).
Summary: Most industrial optimization problems are sparse and can be formulated as block-separable mixed-integer nonlinear programming (MINLP) problems, defined by linking low-dimensional sub-problems by (linear) coupling constraints. Decomposition methods solve a block-separable MINLP by alternately solving master problems and sub-problems. In practice, decomposition methods are sometimes the only possibility to compute high-quality solutions of large-scale optimization problems. However, efficient implementations may require expert knowledge and problem-specific features. Recently, there is a renewed interest in making these methods accessible to general users by developing generic decomposition frameworks and modelling support. The focus of this chapter is on so-called multi-tree decomposition methods, which iteratively approximate the feasible area without using a single (global) branch-and-bound tree, i.e. branch-and-bound is only used for solving sub-problems. After an introduction, we describe first outer approximation (OA) decomposition methods, including the adaptive, multivariate partitioning (AMP) and the novel decomposition-based outer approximation (DECOA) algorithm. This is followed by a description of multi-tree methods using a reduced master problem for solving large-scale industrial optimization problems. The first method to be described applies parallel column generation (CG) and iterative fixing for solving nonconvex transport optimization problems with several hundred millions of variables and constraints. The second method is based on a novel approach combining CG and compact outer approximation. The last methodology to be discussed is the general Benders decomposition method for globally solving large nonconvex stochastic programs using a reduced mixed-integer programming (MIP) master problem.
For the entire collection see [Zbl 1427.90005].
MSC:
90C06 Large-scale problems in mathematical programming
90C11 Mixed integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Belotti, P., Kirches, C., Leyffer, S., Linderoth, J., Luedtke, J., Mahajan, A.: Mixed-integer nonlinear optimization. Acta Numerica pp. 1-131 (2013) · Zbl 1291.65172
[2] Belotti, P., Lee, J., Liberti, L., Margot, F., Wächter, A.: Branching and bounds tightening techniques for non-convex MINLP. Optimization Methods and Software 24(4-5), 597-634 (2009). URL http://www.optimization-online.org/DB_HTML/2008/08/2059.html · Zbl 1179.90237
[3] Ben-Ameur, W., Ouorou, A.: Mathematical models of the delay constrained routing problem. Algorithmic Operations Research 1(2), 94-103 (2006) · Zbl 1186.90116
[4] Berenguel, J., Casado, L., García, I., Hendrix, E.: On estimating workload in interval branch-and-bound global optimization algorithms. Journal of Global Optimization 56(3), 821-844 (2013) · Zbl 1275.90062
[5] Bodur, M., Ahmed, S., Boland, N., Nemhauser, G.L.: Decomposition of loosely coupled integer programs: A multiobjective perspective. http://www.optimization-online.org/DB_FILE/2016/08/5599.pdf (2016)
[6] Borndörfer, R., Löbel, A., Reuther, M., Schlechte, T., Weider, S.: Rapid branching. Public Transport 5, 3-23 (2013)
[7] Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein., J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning 3, 1-122 (2011) · Zbl 1229.90122
[8] Burer, S., Letchford, A.: Non-convex mixed-integer nonlinear programming: A survey. Surveys in Operations Research and Management Science 17 (2), 97-106 (2012)
[9] Bussieck, M.R., Vigerske, S.: MINLP Solver Software. www.math.hu-berlin.de/ stefan/minlpsoft.pdf (2014)
[10] Desrosiers, J., Lübbecke, M.: Selected topics in column generation. Operations Research pp. 1007-1023 (2005) · Zbl 1165.90578
[11] Desrosiers, J., Lübbecke, M.: Branch-price-and-cut algorithms. In: J. Cochran, L. Cox, P. Keskinocak, J. Kharoufeh, J. Smith (eds.) Wiley Encyclopedia of Operations Research and Management Science. John Wiley & Sons, Inc. (2010)
[12] Domschke, P., ler, B.G., Kolb, O., Lang, J., Martin, A., Morsi, A.: Combination of nonlinear and linear optimization of transient gas networks. INFORMS J. Comput. (2011) · Zbl 1243.90030
[13] Drud, A.S., Rosenborg, A.: Dimensioning water distribution networks. Master’s thesis, Technical University of Denmark (1973)
[14] Duran, M., Grossmann, I.: An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Mathematical Programming pp. 307-339 (1986) · Zbl 0619.90052
[15] Feltenmark, S., Kiwiel, K.C.: Dual applications of proximal bundle methods including Lagrangian relaxation of nonconvex problems. SIAM Journal of Optimization 10(3), 697-721 (2000) · Zbl 0958.65070
[16] Fletcher, R., Leyffer, S.: Solving mixed integer nonlinear programs by outer approximation. Mathematical Programming 66(3(A)), 327-349 (1994) · Zbl 0833.90088
[17] Flippo, O.E., Rinnooy-Kan, A.H.G.: Decomposition in general mathematical programming. Mathematical Programming 60, 361-382 (1993) · Zbl 0784.90107
[18] Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite element approximations. Computers and Mathematics with Applications 2, 17-40 (1976) · Zbl 0352.65034
[19] Geissler, B., Morsi, A., Schewe, L., Schmidt, M.: Solving Power-Constrained Gas Transportation Problems using an MIP-based Alternating Direction Method. www.optimization-online.org/DB_HTML/2014/11/4660.html (2014)
[20] Geoffrion, A.: Generalized benders decomposition. Journal of Optimization Theory and Applications 10(4), 237-260 (1972) · Zbl 0229.90024
[21] Geoffrion, A.M.: Lagrangian Relaxation for Integer Programming. Mathematical Programming Studies 2, 82-114 (1974)
[22] Gleixner, A., Eifler, L., Gally, T., Gamrath, G., Gemander, P., Gottwald, R.L., Hendel, G., Hojny, C., Koch, T., Miltenberger, M., Müller, B., Pfetsch, M.E., Puchert, C., Rehfeldt, D., Schlösser, F., Serrano, F., Shinano, Y., Viernickel, J.M., Vigerske, S., Weninger, D., Witt, J.T., Witzig, J.: The SCIP Optimization Suite 5.0. Technical report, www.optimization-online.org/DB_HTML/2017/12/6385.html (2017)
[23] Goderbauer, S., Bahl, B., Voll, P., Lübbecke, M., Bardow, A., Koster, A.: An adaptive discretization MINLP algorithm for optimal synthesis of decentralized energy supply systems. Computers & Chemical Engineering 95, 38-48 (2016)
[24] Hart, W.E., Laird, C.D., Watson, J.P., Woodruff, D.L., Hackebeil, G.A., Nicholson, B.L., Siirola., J.D.: Pyomo-optimization modeling in python, vol. 67, second edn. Springer Science & Business Media (2017) · Zbl 1370.90003
[25] Haverly, C.A.: Studies of the behaviour of recursion for the pooling problem. ACM SIGMAP Bulletin pp. 19 - 28 (1978)
[26] Kronqvist, J., Bernal, D.E., Lundell, A., Grossmann, I.E.: A review and comparison of solvers for convex MINLP. Optimization and Engineering (2018)
[27] Kronqvist, J., Lundell, A., Westerlund, T.: The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming. Journal of Global Optimization 64(2), 249-272 (2016) · Zbl 1339.90247
[28] Lemaréchal, C., Renaud, A.: A geometric study of duality gaps, with applications. Mathematical Programming 90, 399-427 (2001) · Zbl 1039.90087
[29] Leyffer, S., Sartenaer, A., Wanufelle, E.: Branch-and-refine for mixed integer nonconvex global optimization. Tech. rep., Preprint ANL/MCS-P1547-0908,Mathematics and Computer Science Division, Argonne National Laboratory (2008)
[30] Lin, Y., Schrage, L.: The global solver in the LINDO API. Optimization Methods & Software pp. 657-668 (2009) · Zbl 1177.90325
[31] Lundell, A., Kronqvist, J., Westerlund, T.: The supporting hyperplane optimization toolkit. www.optimization-online.org/DB_HTML/2018/06/6680.html (2018) · Zbl 1339.90247
[32] Misener, R., Floudas, C.: ANTIGONE: Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations. Journal of Global Optimization pp. 503-526 (2014) · Zbl 1301.90063
[33] Nagarajan, H., Lu, M., Wang, S., Bent, R., Sundar, K.: An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programs. Journal of Global Optimization (2019) · Zbl 1429.90056
[34] Nowak, I.: Relaxation and Decomposition Methods for Mixed Integer Nonlinear Programming. Birkhäuser (2005) · Zbl 1089.90039
[35] Nowak, I.: A Dynamic Reduce and Generate Approach for Airline Crew Scheduling. www.gerad.ca/colloques/ColumnGeneration2008/slides/IvoNowak.pdf (2008). GERAD International Workshop on Column Generation, Aussois
[36] Nowak, I.: Parallel Decomposition Methods for Nonconvex Optimization - Recent Advances and New Directions (2014). Proceedings of MAGO
[37] Nowak, I.: Column generation based alternating direction methods for solving MINLPs. www.optimization-online.org/DB_HTML/2015/12/5233.html (2015)
[38] Nowak, I., Breitfeld, N., Hendrix, E.M.T., Njacheun-Njanzoua, G.: Decomposition-based inner- and outer-refinement algorithms for global optimization. Journal of Global Optimization 72(2), 305-321 (2018) · Zbl 1417.90122
[39] Nowak, I., Muts, P.: Decomposition-based successive approximation methods for global optimization. Proceedings of LEGO (2018)
[40] Ogbe, E., Li, X.: A joint decomposition method for global optimization of multiscenario nonconvex mixed-integer nonlinear programs. www.arxiv.org/abs/1802.07342 (2018) · Zbl 1432.90092
[41] Ralphs, T., Galati, M.: Decomposition and dynamic cut generation in integer linear programming. Mathematical Programming 106(2), 261-285 (2006) · Zbl 1134.90448
[42] Tawarmalani, M., Sahinidis, N.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer Academic Publishers (2002) · Zbl 1031.90022
[43] Tawarmalani, M., Sahinidis, N.: A polyhedral branch-and-cut approach to global optimization. Mathematical Programming pp. 225-249 (2005) · Zbl 1099.90047
[44] Uzawa, H.: Iterative methods for concave programming, pp. 154-165. Stanford University Press (1958)
[45] Vigerske, S.: Decomposition in Multistage Stochastic Programming and a Constraint Integer Programming Approach to Mixed-Integer Nonlinear Programming. Ph.D. thesis, Humboldt-Universität zu Berlin (2012)
[46] Vigerske, S.: MINLPLib. http://minlplib.org/index.html (2018)
[47] Wächter, A., Lorenz, B.T.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming 106(1), 25-57 (2006) · Zbl 1134.90542
[48] Westerlund, T., Petterson, F.: An extended cutting plane method for solving convex MINLP problems. Computers and Chemical Engineering 21, 131-
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.