×

Decomposition-based inner- and outer-refinement algorithms for global optimization. (English) Zbl 1417.90122

Summary: Traditional deterministic global optimization methods are often based on a branch-and-bound (BB) search tree, which may grow rapidly, preventing the method to find a good solution. Motivated by decomposition-based inner approximation (column generation) methods for solving transport scheduling problems with over 100 million variables, we present a new deterministic decomposition-based successive approximation method for general modular and/or sparse MINLPs. The new method, called decomposition-based inner- and outer-Refinement, is based on a block-separable reformulation of the model into sub-models. It generates inner- and outer-approximations using column generation, which are successively refined by solving many easier MINLP and MIP subproblems in parallel (using BB), instead of searching over one (global) BB search tree. We present preliminary numerical results with Decogo (decomposition-based global optimizer), a new parallel decomposition MINLP solver implemented in Python and Pyomo.

MSC:

90C26 Nonconvex programming, global optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adjiman, C.S., Androulakis, I.P., Maranas, C.D., Floudas, C.A.: \(\alpha \)-BB. http://titan.princeton.edu (2002)
[2] Belotti, P.; Kirches, C.; Leyffer, S.; Linderoth, J.; Luedtke, J.; Mahajan, A., Mixed-integer nonlinear optimization, Acta Numer., 22, 1-131, (2013) · Zbl 1291.65172 · doi:10.1017/S0962492913000032
[3] Belotti, P.; Lee, J.; Liberti, L.; Margot, F.; Wächter, A., Branching and bounds tightening techniques for non-convex MINLP, Optim. Methods Softw., 24, 597-634, (2009) · Zbl 1179.90237 · doi:10.1080/10556780903087124
[4] Ben-Tal, A.; Eiger, G.; Gershovitz, V., Global minimization by reducing the duality gap, Math. Program., 63, 193-212, (1994) · Zbl 0807.90101 · doi:10.1007/BF01582066
[5] Borndörfer, R.; Löbel, A.; Reuther, M.; Schlechte, T.; Weider, S., Rapid branching, Public Transp., 5, 3-23, (2013) · doi:10.1007/s12469-013-0066-8
[6] Burer, S.; Letchford, A., Non-convex mixed-integer nonlinear programming: a survey, Surv. Oper. Res. Manag. Sci., 17, 97-106, (2012)
[7] Bussieck, M. R., Vigerske, S.: MINLP solver software. http://www.math.hu-berlin.de/ stefan/minlpsoft.pdf (2014)
[8] Desrosiers, J.; Lübbecke, M.; Cochran, J. (ed.); Cox, L. (ed.); Keskinocak, P. (ed.); Kharoufeh, J. (ed.); Smith, J. (ed.), Branch-price-and-cut algorithms, (2010), New York
[9] Desrosiers, J.; Lübbecke, ME, Selected topics in column generation, Oper. Res., 53, 1007-1023, (2005) · Zbl 1165.90578 · doi:10.1287/opre.1050.0234
[10] Domschke, P.; Geißler, B.; Kolb, O.; Lang, J.; Martin, A.; Morsi, A., Combination of nonlinear and linear optimization of transient gas networks, INFORMS J. Comput., 23, 605-617, (2011) · Zbl 1243.90030 · doi:10.1287/ijoc.1100.0429
[11] Duran, M.; Grossmann, I., An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Math. Program., 36, 307-339, (1986) · Zbl 0619.90052 · doi:10.1007/BF02592064
[12] Engineer, F., Nemhauser, G., Savelsbergh, M.: Shortest path based column generation on large networks with many resource constraints. Technical report, Georgia Tech (2008)
[13] Feltenmark, S.; Kiwiel, Krzysztof C., Dual applications of proximal bundle methods including lagrangian relaxation of nonconvex problems, SIAM J. Optim., 10, 697-721, (2000) · Zbl 0958.65070 · doi:10.1137/S1052623498332336
[14] Fletcher, R.; Leyffer, S., Solving mixed integer nonlinear programs by outer approximation, Math. Program., 66, 327-349, (1994) · Zbl 0833.90088 · doi:10.1007/BF01581153
[15] Flippo, OE; Rinnoy Kan, AHG, Decomposition in general mathematical programming, Math. Program., 60, 361-382, (1993) · Zbl 0784.90107 · doi:10.1007/BF01580620
[16] Geoffrion, AM, General Benders decomposition, J. Optim. Theory Appl., 10, 237-260, (1972) · Zbl 0229.90024 · doi:10.1007/BF00934810
[17] Geoffrion, AM, Lagrangian relaxation for integer programming, Math. Program. Stud., 2, 82-114, (1974) · doi:10.1007/BFb0120690
[18] 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, Comput. Chem. Eng., 95, 38-48, (2016) · doi:10.1016/j.compchemeng.2016.09.008
[19] Hart, W., Laird, C., Watson, J.P., Woodruff, D.: Pyomo—Optimization Modeling in Python, vol. 67. Springer, Berlin (2012) · Zbl 1233.90002 · doi:10.1007/978-1-4614-3226-5
[20] Houska, B., Frasch, J., Diehl, M.: An augmented Lagrangian based algorithm for distributed non-convex optimization. http://www.optimization-online.org/DB_HTML/2014/07/4427.html (2014) · Zbl 1345.90069
[21] Koch, T.; Ralphs, T.; Shinano, Y., What could a million cores do to solve integer programs?, Math. Methods Oper. Res., 76, 67-93, (2012) · Zbl 1262.90106 · doi:10.1007/s00186-012-0390-9
[22] Kojima, M., Matsumoto, T., Shid, M.: Moderate nonconvexity = convexity + quadratic concavity. Technical report. http://www.is.titech.ac.jp/ kojima/sdp.html (1999) · Zbl 0957.90508
[23] Lemaréchal, C.; Renaud, A., A geometric study of duality gaps, with applications, Math. Program., 90, 399-427, (2001) · Zbl 1039.90087 · doi:10.1007/PL00011429
[24] Leyffer, S., Sartenaer, A., Wanufelle, E.: Branch-and-refine for mixed integer nonconvex global optimization. Technical report, Preprint ANL/MCS-P1547-0908, Mathematics and Computer Science Division, Argonne National Laboratory (2008)
[25] Lin, Y.; Schrage, L., The global solver in the LINDO API, Optim. Methods Softw., 24, 657-668, (2009) · Zbl 1177.90325 · doi:10.1080/10556780902753221
[26] Misener, R.; Floudas, C., ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations, J. Glob. Optim., 59, 503-526, (2014) · Zbl 1301.90063 · doi:10.1007/s10898-014-0166-2
[27] Nowak, I.: Relaxation and Decomposition Methods for Mixed Integer Nonlinear Programming. Birkhäuser, Basel (2005) · Zbl 1089.90039
[28] Nowak, I.: A dynamic reduce and generate approach for airline crew scheduling. GERAD International Workshop on Column Generation, Aussois. http://www.gerad.ca/colloques/ColumnGeneration2008/slides/IvoNowak.pdf (2008)
[29] Nowak, I.: Parallel decomposition methods for nonconvex optimization—recent advances and new directions. In: Proceedings of MAGO (2014)
[30] Nowak, I.: Column generation based alternating direction methods for solving MINLPs. http://www.optimization-online.org/DB_HTML/2015/12/5233.html (2015)
[31] Ralphs, T.; Galati, M., Decomposition and dynamic cut generation in integer linear programming, Math. Program., 106, 261-285, (2006) · Zbl 1134.90448 · doi:10.1007/s10107-005-0606-3
[32] Tawarmalani, M.; Sahinidis, N., A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249, (2005) · Zbl 1099.90047 · doi:10.1007/s10107-005-0581-8
[33] 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) · Zbl 1031.90022 · doi:10.1007/978-1-4757-3532-1
[34] 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)
[35] Vigerske, S.: MINLP Library 2. http://www.gamsworld.org/minlp/minlplib2/html (2017)
[36] Wächter, A.: An interior point algorithm for large-scale nonlinear optimization with applications in process engineering. Ph.D. thesis, Carnegie Mellon University, Pittsburgh, USA. http://researcher.watson.ibm.com/researcher/files/us-andreasw/thesis.pdf (2002)
[37] Westerlund, T.; Petterson, F., An extended cutting plane method for solving convex MINLP problems, Compu. Chem. Eng., 21, 131-136, (1995) · doi:10.1016/0098-1354(95)87027-X
[38] Yuan, X.; Zhang, S.; Piboleau, L.; Domenech, S., Une methode d’optimisation nonlineare en variables mixtes pour la conception de procedes, RAIRO, 22, 331, (1988) · Zbl 0656.90071 · doi:10.1051/ro/1988220403311
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.