Polyhedral approximation strategies for nonconvex mixed-integer nonlinear programming in SHOT. (English) Zbl 1490.90200
Summary: Different versions of polyhedral outer approximation are used by many algorithms for mixed-integer nonlinear programming (MINLP). While it has been demonstrated that such methods work well for convex MINLP, extending them to solve nonconvex problems has traditionally been challenging. The Supporting Hyperplane Optimization Toolkit (SHOT) is a solver based on polyhedral approximations of the nonlinear feasible set of MINLP problems. SHOT is an open source COIN-OR project, and is currently one of the most efficient global solvers for convex MINLP. In this paper, we discuss some extensions to SHOT that significantly extend its applicability to nonconvex problems. The functionality include utilizing convexity detection for selecting the nonlinearities to linearize, lifting reformulations for special classes of functions, feasibility relaxations for infeasible subproblems and adding objective cuts to force the search for better feasible solutions. This functionality is not unique to SHOT, but can be implemented in other similar methods as well. In addition to discussing the new nonconvex functionality of SHOT, an extensive benchmark of deterministic solvers for nonconvex MINLP is performed that provides a snapshot of the current state of nonconvex MINLP.
Keywords:
nonconvex MINLP; Supporting Hyperplane Optimization Toolkit (SHOT); polyhedral outer approximation; reformulation techniques; local and global MINLP techniques; feasibility relaxationSoftware:
JuMP; SUSPECT; Muriqui; MINOTAUR; Decogo; ROSE; Juniper; Eigen; FEASPUMP; SHOT; MINLPLib; Bonmin; LINDOGlobal; MINLP; ANTIGONE; GAMS; AlphaECP; Pyomo; LINDO; PAVER; DICOPT; Ipopt; Gurobi; Benchmarks for Optimization Software; SCIPReferences:
| [1] | Belotti, P.; Berthold, T., Three ideas for a feasibility pump for nonconvex MINLP, Optim. Lett., 11, 1, 3-15 (2017) · Zbl 1373.90080 |
| [2] | 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 |
| [3] | Bernal, DE; Vigerske, S.; Trespalacios, F.; Grossmann, IE, Improving the performance of DICOPT in convex MINLP problems using a feasibility pump, Optim. Methods Softw., 35, 1, 171-190 (2020) · Zbl 1425.90070 |
| [4] | Berthold, T.: Heuristic algorithms in global MINLP solvers. Ph.D. thesis, Technische Universität Berlin (2014) |
| [5] | Bonami, P., Kilinç, M., Linderoth, J.: Algorithms and software for convex mixed integer nonlinear programs. In: Mixed integer nonlinear programming, pp. 1-39. Springer (2012) · Zbl 1242.90121 |
| [6] | Bonami, P.; Lee, J., BONMIN user’s manual, Numer. Math., 4, 1-32 (2007) |
| [7] | Boukouvala, F.; Misener, R.; Floudas, CA, Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO, Eur. J. Op. Res., 252, 3, 701-727 (2016) · Zbl 1346.90677 |
| [8] | Bussieck, MR; Dirkse, SP; Vigerske, S., PAVER 2.0: an open source environment for automated performance analysis of benchmarking data, J. Global Optim., 59, 2, 259-275 (2014) · Zbl 1300.90003 |
| [9] | Bussieck, M.R., Vigerske, S.: MINLP solver software. In: Wiley encyclopedia of operations research and management science. Wiley Online Library (2010) |
| [10] | Castro, PM, Tightening piecewise mccormick relaxations for bilinear problems, Comput. Chem. Eng., 72, 300-311 (2015) |
| [11] | Ceccon, F.; Siirola, JD; Misener, R., SUSPECT: MINLP special structure detector for pyomo, Optimization Letters, 14, 801-814 (2019) · Zbl 1444.90081 |
| [12] | Dakin, RJ, A tree-search algorithm for mixed integer programming problems, Comput. J., 8, 3, 250-255 (1965) · Zbl 0154.42004 |
| [13] | D’Ambrosio, C.; Frangioni, A.; Liberti, L.; Lodi, A., A storm of feasibility pumps for nonconvex MINLP, Math. Program., 136, 2, 375-402 (2012) · Zbl 1257.90056 |
| [14] | D’Ambrosio, C.; Lodi, A., Mixed integer nonlinear programming tools: an updated practical overview, Ann. Op. Res., 204, 1, 301-320 (2013) · Zbl 1269.90067 |
| [15] | Dunning, I.; Huchette, J.; Lubin, M., JuMP: a modeling language for mathematical optimization, SIAM Rev., 59, 2, 295-320 (2017) · Zbl 1368.90002 |
| [16] | Duran, MA; Grossmann, IE, An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Math. Program., 36, 3, 307-339 (1986) · Zbl 0619.90052 |
| [17] | D’Ambrosio, C.; Lodi, A.; Martello, S., Piecewise linear approximation of functions of two variables in MILP models, Op. Res. Lett., 38, 1, 39-46 (2010) · Zbl 1182.90064 |
| [18] | Fischetti, M.; Glover, F.; Lodi, A., The feasibility pump, Math. Program., 104, 1, 91-104 (2005) · Zbl 1077.90039 |
| [19] | Fischetti, M.; Monaci, M., A branch-and-cut algorithm for mixed-integer bilinear programming, Eur. J. Op. Res., 282, 2, 506-514 (2020) · Zbl 1430.90431 |
| [20] | Fletcher, R.; Leyffer, S., Solving mixed integer nonlinear programs by outer approximation, Math. Program., 66, 1, 327-349 (1994) · Zbl 0833.90088 |
| [21] | Floudas, C.A.: Deterministic global optimization, vol. 37 of nonconvex optimization and its applications (2000) · Zbl 0980.49027 |
| [22] | Fourer, R.; Gay, D.; Kernighan, B., AMPL (1993), MA: Boyd & Fraser Danvers, MA |
| [23] | GAMS: Solver manuals (2018). https://www.gams.com/latest/docs/S_MAIN.html |
| [24] | Geoffrion, AM, Generalized benders decomposition, J. Optim. Theory Appl., 10, 4, 237-260 (1972) · Zbl 0229.90024 |
| [25] | Gleixner, A., Bastubbe, M., Eifler, L., Gally, T., Gamrath, G., Gottwald, R.L., Hendel, G., Hojny, C., Koch, T., Lübbecke, M.E., Maher, S.J., Miltenberger, M., Müller, B., Pfetsch, M.E., Puchert, C., Rehfeldt, D., Schlösser, F., Schubert, C., Serrano, F., Shinano, Y., Viernickel, J.M., Walter, M., Wegscheider, F., Witt, J.T., Witzig, J.: The SCIP Optimization Suite 6.0. Technical report, Optimization Online (2018) |
| [26] | Gounaris, CE; Misener, R.; Floudas, CA, Computational comparison of piecewise- linear relaxations for pooling problems, Ind. Eng. Chem. Res., 48, 12, 5742-5766 (2009) |
| [27] | Grossmann, I.E., Kravanja, Z.: Mixed-integer nonlinear programming: A survey of algorithms and applications. In: L.T. Biegler, T.F. Coleman, A.R. Conn, F.N. Santosa (eds.) Large-scale optimization with applications, pp. 73-100. Springer (1997) · Zbl 0884.65058 |
| [28] | Grossmann, I.E., Viswanathan, J., Vecchietti, A., Raman, R., Kalvelagen, E., et al.: GAMS/DICOPT: A discrete continuous optimization package. GAMS Corporation Inc (2002) |
| [29] | Guennebaud, G., Jacob, B., et al.: Eigen v3 (2010). http://eigen.tuxfamily.org |
| [30] | Gupta, OK; Ravindran, A., Branch and bound experiments in convex nonlinear integer programming, Manag. Sci., 31, 12, 1533-1546 (1985) · Zbl 0591.90065 |
| [31] | Gurobi Optimization: Gurobi optimizer reference manual (2020). https://www.gurobi.com/wp-content/plugins/hd_documentations/documentation/9.0/refman.pdf |
| [32] | Hart, WE; Laird, CD; Watson, JP; Woodruff, DL; Hackebeil, GA; Nicholson, BL; Siirola, JD, Pyomo-optimization modeling in Python (2012), Berlin: Springer, Berlin · Zbl 1370.90003 |
| [33] | Kocis, GR; Grossmann, IE, Computational experience with DICOPT solving MINLP problems in process systems engineering, Comp. Chem. Eng., 13, 3, 307-315 (1989) |
| [34] | Kronqvist, J., Bernal, D., Lundell, A., Westerlund, T.: A center-cut algorithm for quickly obtaining feasible solutions and solving convex MINLP problems. Comp. Chem. Eng. (2018) |
| [35] | Kronqvist, J., Bernal, D.E., Grossmann, I.E.: Using regularization and second order information in outer approximation for convex MINLP. Mathematical Programming p. 285-310 (2020) · Zbl 1461.65168 |
| [36] | Kronqvist, J., Bernal, D.E., Lundell, A., Grossmann, I.E.: A review and comparison of solvers for convex MINLP. Optimization and Engineering pp. 1-59 (2018) |
| [37] | Kronqvist, J.; Lundell, A.; Westerlund, T., The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming, J. Global Optim., 64, 2, 249-272 (2016) · Zbl 1339.90247 |
| [38] | Kronqvist, J., Lundell, A., Westerlund, T.: A center-cut algorithm for solving convex mixed-integer nonlinear programming problems. In: Computer Aided Chemical Engineering, vol. 40, pp. 2131-2136. Elsevier (2017) |
| [39] | Kronqvist, J.; Lundell, A.; Westerlund, T., Reformulations for utilizing separability when solving convex minlp problems, J. Global Optim., 71, 3, 571-592 (2018) · Zbl 1402.90098 |
| [40] | Kröger, O., Coffrin, C., Hijazi, H., Nagarajan, H.: Juniper: An open-source nonlinear branch-and-bound solver in julia. In: Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp. 377-386. Springer International Publishing (2018) · Zbl 1511.90001 |
| [41] | Lastusilta, T.: GAMS MINLP solver comparisons and some improvements to the AlphaECP algorithm. PhD thesis, Åbo Akademi University (2011) |
| [42] | Leyffer, S., Linderoth, J., Luedtke, J., Miller, A., Munson, T.: Applications and algorithms for mixed integer nonlinear programming. In: Journal of Physics: Conference Series, vol. 180, p. 012014. IOP Publishing (2009) |
| [43] | Liberti, L.: Reformulation techniques in mathematical programming. HDR thesis (2009) · Zbl 1170.90304 |
| [44] | Liberti, L.; Cafieri, S.; Tarissan, F.; Abraham, A.; Hassanien, AE; Siarry, P.; Engelbrecht, A., Reformulations in mathematical programming: a computational approach, Foundations of Computational Intelligence Volume 3: Global Optimization, 153-234 (2009), Berlin Heidelberg, Berlin, Heidelberg: Springer, Berlin Heidelberg, Berlin, Heidelberg |
| [45] | Liberti, L., Nannicini, G., Mladenović, N.: A good recipe for solving MINLPs. In: Matheuristics, pp. 231-244. Springer (2009) · Zbl 1276.90041 |
| [46] | Lin, Y.; Schrage, L., The global solver in the LINDO API, Optim. Methods Softw., 24, 4-5, 657-668 (2009) · Zbl 1177.90325 |
| [47] | Lundell, A.: Transformation techniques for signomial functions in global optimization. Ph.D. thesis, Åbo Akademi University (2009) |
| [48] | Lundell, A., Kronqvist, J.: On solving nonconvex MINLP problems with SHOT. In: World Congress on Global Optimization, pp. 448-457. Springer, Cham (2019) |
| [49] | Lundell, A.; Kronqvist, J.; Westerlund, T., The Supporting Hyperplane Optimization Toolkit (2020), Optimization Online: Preprint, Optimization Online · Zbl 1339.90247 |
| [50] | Lundell, A.; Skjäl, A.; Westerlund, T., A reformulation framework for global optimization, J. Global Optim., 57, 1, 115-141 (2013) · Zbl 1277.90102 |
| [51] | Lundell, A.; Westerlund, J.; Westerlund, T., Some transformation techniques with applications in global optimization, J. Global Optim., 43, 2-3, 391-405 (2009) · Zbl 1169.90453 |
| [52] | Lundell, A., Westerlund, T.: Representation of the convex envelope of bilinear terms in a reformulation framework for global optimization. In: 12th International Symposium on Process Systems Engineering and 25th European Symposium on Computer Aided Process Engineering, pp. 833-838. Elsevier (2015) |
| [53] | Lundell, A.; Westerlund, T., Solving global optimization problems using reformulations and signomial transformations, Comp. Chem. Eng., 116, 122-134 (2018) |
| [54] | Mahajan, A.; Leyffer, S.; Linderoth, J.; Luedtke, J.; Munson, T., Minotaur: A Mixed-Integer Nonlinear Optimization Toolkit (2017), Optimization Online: Preprint, Optimization Online · Zbl 1476.65099 |
| [55] | Melo, W., Fampa, M., Raupp, F.: An overview of MINLP algorithms and their implementation in Muriqui Optimizer. Annals of Operations Research pp. 1-25 (2018) · Zbl 1443.90256 |
| [56] | Messine, F., Deterministic global optimization using interval constraint propagation techniques, RAIRO Op. Res., 38, 4, 277-293 (2004) · Zbl 1114.90156 |
| [57] | MINLPLib: Mixed-integer nonlinear programming library (2020). http://www.minlplib.org/. [Downloaded January 6th 2020] |
| [58] | Misener, R.; Floudas, CA, Piecewise-linear approximations of multidimensional functions, J. Optim. Theory Appl., 145, 120-147 (2010) · Zbl 1186.90080 |
| [59] | Misener, R.; Floudas, CA, ANTIGONE: Algorithms for continuous/integer global optimization of nonlinear equations, J. Global Optim., 59, 2-3, 503-526 (2014) · Zbl 1301.90063 |
| [60] | Mittelmann, H.: Benchmarks for optimization software (2018). http://plato.asu.edu/bench.html. [Accessed 28-Jan-2020] |
| [61] | Muts, P., Nowak, I., Hendrix, E.M.: The decomposition-based outer approximation algorithm for convex mixed-integer nonlinear programming. Journal of Global Optimization pp. 1-22 (2020) · Zbl 1441.90100 |
| [62] | Nagarajan, H.; Lu, M.; Wang, S.; Bent, R.; Sundar, K., An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programs, J. Global Optim., 74, 639-675 (2019) · Zbl 1429.90056 |
| [63] | Nowak, I., Breitfeld, N., Hendrix, E.M., Njacheun-Njanzoua, G.: Decomposition-based inner-and outer-refinement algorithms for global optimization. Journal of Global Optimization pp. 1-17 (2018) · Zbl 1417.90122 |
| [64] | Schichl, H.; Neumaier, A., Interval analysis on directed acyclic graphs for global optimization, J. Global Optim., 33, 4, 541-562 (2005) · Zbl 1094.65061 |
| [65] | Su, L.; Tang, L.; Bernal, DE; Grossmann, IE, Improved quadratic cuts for convex mixed-integer nonlinear programs, Comput. Chem. Eng., 109, 77-95 (2018) |
| [66] | Sundar, K., Nagarajan, H., Wang, S., Linderoth, J., Bent, R.: Piecewise polyhedral formulations for a multilinear term (2020) · Zbl 1525.90443 |
| [67] | Tawarmalani, M., Sahinidis, N.V.: Convexification and global optimization in continuous and mixed-integer nonlinear programming: Theory, algorithms, software, and applications, vol. 65. Springer Science & Business Media (2002) · Zbl 1031.90022 |
| [68] | Tawarmalani, M.; Sahinidis, NV, Global optimization of mixed-integer nonlinear programs: a theoretical and computational study, Math. Program., 99, 3, 563-591 (2004) · Zbl 1062.90041 |
| [69] | Tawarmalani, M.; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249 (2005) · Zbl 1099.90047 |
| [70] | Trespalacios, F.; Grossmann, IE, Review of mixed-integer nonlinear and generalized disjunctive programming methods, Chem. Ingenieur Technik, 86, 7, 991-1012 (2014) |
| [71] | Vigerske, S.; Gleixner, A., SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework, Optim. Methods Softw., 33, 3, 563-593 (2018) · Zbl 1398.90112 |
| [72] | Viswanathan, J.; Grossmann, IE, A combined penalty function and outer-approximation method for MINLP optimization, Comput. Chem. Eng., 14, 7, 769-782 (1990) |
| [73] | Wächter, A.; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 1, 25-57 (2006) · Zbl 1134.90542 |
| [74] | Westerlund, T.; Petterson, F., An extended cutting plane method for solving convex MINLP problems, Comput. Chem. Eng., 19, 131-136 (1995) |
| [75] | Westerlund, T.; Pörn, R., Solving pseudo-convex mixed integer optimization problems by cutting plane techniques, Optim. Eng., 3, 3, 253-280 (2002) · Zbl 1035.90051 |
| [76] | Wicaksono, DS; Karimi, IA, Piecewise milp under- and overestimators for global optimization of bilinear programs, AIChE J., 54, 4, 991-1008 (2008) |
| [77] | Zhou, K.; Kılınç, MR; Chen, X.; Sahinidis, NV, An efficient strategy for the activation of MIP relaxations in a multicore global MINLP solver, J. Global Optim., 70, 3, 497-516 (2018) · Zbl 1393.90076 |
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.
