A computational study of perspective cuts. (English) Zbl 1528.90003
Summary: The benefits of cutting planes based on the perspective function are well known for many specific classes of mixed-integer nonlinear programs with on/off structures. However, we are not aware of any empirical studies that evaluate their applicability and computational impact over large, heterogeneous test sets in general-purpose solvers. This paper provides a detailed computational study of perspective cuts within a linear programming based branch-and-cut solver for general mixed-integer nonlinear programs. Within this study, we extend the applicability of perspective cuts from convex to nonconvex nonlinearities. This generalization is achieved by applying a perspective strengthening to valid linear inequalities which separate solutions of linear relaxations. The resulting method can be applied to any constraint where all variables appearing in nonlinear terms are semi-continuous and depend on at least one common indicator variable. Our computational experiments show that adding perspective cuts for convex constraints yields a consistent improvement of performance, and adding perspective cuts for nonconvex constraints reduces branch-and-bound tree sizes and strengthens the root node relaxation, but has no significant impact on the overall mean time.
MSC:
| 90-04 | Software, source code, etc. for problems pertaining to operations research and mathematical programming |
| 90-05 | Experimental work for problems pertaining to operations research and mathematical programming |
| 90-08 | Computational methods for problems pertaining to operations research and mathematical programming |
| 90C11 | Mixed integer programming |
| 90C26 | Nonconvex programming, global optimization |
| 90C30 | Nonlinear programming |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
Keywords:
perspective cuts; mixed integer nonlinear programming; nonconvex optimization; computational studyReferences:
| [1] | Aktürk, MS; Atamtürk, A.; Gürel, S., A strong conic quadratic reformulation for machine-job assignment with controllable processing times, Oper. Res. Lett., 37, 3, 187-191 (2009) · Zbl 1167.90518 · doi:10.1016/j.orl.2008.12.009 |
| [2] | Atamtürk, A.; Gómez, A., Strong formulations for quadratic optimization with M-matrices and indicator variables, Math. Program., 170, 1, 141-176 (2018) · Zbl 1391.90423 · doi:10.1007/s10107-018-1301-5 |
| [3] | Balas, E., Disjunctive programming, Ann. Discrete Math., 5, 3-51 (1979) · Zbl 0409.90061 · doi:10.1016/S0167-5060(08)70342-X |
| [4] | Balas, E., Disjunctive programming and a hierarchy of relaxations for discrete optimization problems, SIAM J. Algebr. Discrete Methods, 6, 3, 466-486 (1985) · Zbl 0592.90070 · doi:10.1137/0606047 |
| [5] | Barbaro, R.; Ramani, R., Generalized multiperiod MIP model for production scheduling and processing facilities selection and location, Min. Eng., 38, 2, 107-114 (1986) |
| [6] | Bestuzheva, K.: KBestuzheva/SCIP-perspective-cuts: implementation of perspective cuts in SCIP (2023). doi:10.5281/zenodo.8134526 |
| [7] | Bestuzheva, K.; Besançon, M.; Chen, WK; Chmiela, A.; Donkiewicz, T.; van Doornmalen, J.; Eifler, L.; Gaul, O.; Gamrath, G.; Gleixner, A.; Gottwald, L.; Graczyk, C.; Halbig, K.; Hoen, A.; Hojny, C.; van der Hulst, R.; Koch, T.; Lübbecke, M.; Maher, S.; Matter, F.; Mühmer, E.; Müller, B.; Pfetsch, M.; Rehfeldt, D.; Schlein, S.; Schlösser, F.; Serrano, F.; Shinano, Y.; Sofranac, B.; Turner, M.; Vigerske, S.; Wegscheider, F.; Wellner, P.; Weninger, D.; Witzig, J., Enabling research through the SCIP optimization Suite 8.0, ACM Trans. Math. Softw. (2023) · Zbl 07910037 · doi:10.1145/3585516 |
| [8] | Bestuzheva, K.; Hijazi, H.; Coffrin, C., Convex relaxations for quadratic on/off constraints and applications to optimal transmission switching, INFORMS J. Comput., 32, 3, 682-696 (2020) · Zbl 1474.90435 · doi:10.1287/ijoc.2019.0900 |
| [9] | Bussieck, MR; Drud, AS; Meeraus, A., MINLPLib: a collection of test models for mixed-integer nonlinear programming, INFORMS J. Comput., 15, 1, 114-119 (2003) · Zbl 1238.90104 · doi:10.1287/ijoc.15.1.114.15159 |
| [10] | Ceria, S.; Soares, J., Convex programming for disjunctive convex optimization, Math. Program., 86, 3, 595-614 (1999) · Zbl 0954.90049 · doi:10.1007/s101070050106 |
| [11] | Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263 |
| [12] | Fisher, EB; O’Neill, RP; Ferris, MC, Optimal transmission switching, IEEE Trans. Power Syst., 23, 3, 1346-1355 (2008) · doi:10.1109/TPWRS.2008.922256 |
| [13] | Frangioni, A.; Furini, F.; Gentile, C., Approximated perspective relaxations: a project and lift approach, Comput. Optim. Appl., 63, 3, 705-735 (2016) · Zbl 1362.90301 · doi:10.1007/s10589-015-9787-8 |
| [14] | Frangioni, A.; Furini, F.; Gentile, C., Improving the approximated projected perspective reformulation by dual information, Oper. Res. Lett., 45, 5, 519-524 (2017) · Zbl 1409.90115 · doi:10.1016/j.orl.2017.08.001 |
| [15] | Frangioni, A.; Gentile, C., Perspective cuts for a class of convex 0-1 mixed integer programs, Math. Program., 106, 2, 225-236 (2006) · Zbl 1134.90447 · doi:10.1007/s10107-005-0594-3 |
| [16] | Frangioni, A.; Gentile, C., SDP diagonalizations and perspective cuts for a class of nonseparable MIQP, Oper. Res. Lett., 35, 2, 181-185 (2007) · Zbl 1149.90379 · doi:10.1016/j.orl.2006.03.008 |
| [17] | Frangioni, A.; Gentile, C., A computational comparison of reformulations of the perspective relaxation: SOCP vs. cutting planes, Oper. Res. Lett., 37, 3, 206-210 (2009) · Zbl 1167.90604 · doi:10.1016/j.orl.2009.02.003 |
| [18] | Frangioni, A.; Gentile, C.; Grande, E.; Pacifici, A., Projected perspective reformulations with applications in design problems, Oper. Res., 59, 5, 1225-1232 (2011) · Zbl 1235.90148 · doi:10.1287/opre.1110.0930 |
| [19] | Frangioni, A.; Gentile, C.; Hungerford, J., Decompositions of semidefinite matrices and the perspective reformulation of nonseparable quadratic programs, Math. Oper. Res., 45, 1, 15-33 (2020) · Zbl 1437.90110 · doi:10.1287/moor.2018.0969 |
| [20] | Furini, F.; Traversi, E.; Belotti, P.; Frangioni, A.; Gleixner, A.; Gould, N.; Liberti, L.; Lodi, A.; Misener, R.; Mittelmann, H., QPLIB: a library of quadratic programming instances, Math. Program. Comput., 11, 2, 237-265 (2019) · Zbl 1435.90099 · doi:10.1007/s12532-018-0147-4 |
| [21] | Furman, KC; Sawaya, NW; Grossmann, IE, A computationally useful algebraic representation of nonlinear disjunctive convex sets using the perspective function, Comput. Optim. Appl., 76, 2, 589-614 (2020) · Zbl 1453.90119 · doi:10.1007/s10589-020-00176-0 |
| [22] | Gamrath, G., Anderson, D., Bestuzheva, K., Chen, W.K., Eifler, L., Gasse, M., Gemander, P., Gleixner, A., Gottwald, L., Halbig, K., et al.: The SCIP Optimization Suite 7.0. ZIB-Report 20-10, Zuse Institute Berlin (2020) |
| [23] | Gómez, A., Strong formulations for conic quadratic optimization with indicator variables, Math. Program., 188, 1, 193-226 (2021) · Zbl 1470.90056 · doi:10.1007/s10107-020-01508-y |
| [24] | Grossmann, IE; Lee, S., Generalized convex disjunctive programming: Nonlinear convex hull relaxation, Comput. Optim. Appl., 26, 1, 83-100 (2003) · Zbl 1030.90069 · doi:10.1023/A:1025154322278 |
| [25] | Günlük, O.; Linderoth, J., Perspective reformulations of mixed integer nonlinear programs with indicator variables, Math. Program., 124, 1-2, 183-205 (2010) · Zbl 1229.90106 · doi:10.1007/s10107-010-0360-z |
| [26] | Günlük, O., Linderoth, J.: Perspective reformulation and applications. In: J. Lee, S. Leyffer (eds.) Mixed Integer Nonlinear Programming, pp. 61-89. Springer, New York, NY (2012). doi:10.1007/978-1-4614-1927-3_3 · Zbl 1242.90134 |
| [27] | Hijazi, H.; Bonami, P.; Cornuéjols, G.; Ouorou, A., Mixed integer nonlinear programs featuring “on/off” constraints: convex analysis and applications, Electron. Notes Discrete Math., 36, 1153-1160 (2010) · Zbl 1274.90382 · doi:10.1016/j.endm.2010.05.146 |
| [28] | Hijazi, H.; Bonami, P.; Cornuéjols, G.; Ouorou, A., Mixed-integer nonlinear programs featuring “on/off” constraints, Comput. Optim. Appl., 52, 2, 537-558 (2012) · Zbl 1250.90058 · doi:10.1007/s10589-011-9424-0 |
| [29] | Kelley, JE Jr, The cutting-plane method for solving convex programs, J. Soc. Ind. Appl. Math., 8, 4, 703-712 (1960) · Zbl 0098.12104 · doi:10.1137/0108053 |
| [30] | Khajavirad, A.; Sahinidis, NV, Convex envelopes generated from finitely many compact convex sets, Math. Program., 137, 1-2, 371-408 (2013) · Zbl 1284.90055 · doi:10.1007/s10107-011-0496-5 |
| [31] | Lodi, A., Tramontani, A.: Performance variability in mixed-integer programming. In: Theory Driven by Influential Applications, pp. 1-12. INFORMS (2013). doi:10.1287/educ.2013.0112 |
| [32] | Rockafellar, R.T.: Convex analysis. Princeton University Press (2015) |
| [33] | Salgado, E., Gentile, C., Liberti, L.: Perspective cuts for the ACOPF with generators. In: New Trends in Emerging Complex Real Life Problems, pp. 451-461. Springer (2018) |
| [34] | Salgado, E.; Scozzari, A.; Tardella, F.; Liberti, L.; Lee, J.; Rinaldi, G.; Mahjoub, AR, Alternating current optimal power flow with generator selection, Combinatorial Optimization, 364-375 (2018), Cham: Springer International Publishing, Cham · Zbl 1403.90647 · doi:10.1007/978-3-319-96151-4_31 |
| [35] | Stubbs, RA; Mehrotra, S., A branch-and-cut method for 0-1 mixed convex programming, Math. Program., 86, 3, 515-532 (1999) · Zbl 0946.90054 · doi:10.1007/s101070050103 |
| [36] | Tawarmalani, M.; Richard, JPP; Chung, K., Strong valid inequalities for orthogonal disjunctions and bilinear covering sets, Math. Program., 124, 1-2, 481-512 (2010) · Zbl 1198.90298 · doi:10.1007/s10107-010-0374-6 |
| [37] | Tawarmalani, M.; Sahinidis, NV, Convex extensions and envelopes of lower semi-continuous functions, Math. Program., 93, 2, 247-263 (2002) · Zbl 1065.90062 · doi:10.1007/s10107-002-0308-z |
| [38] | 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 · doi:10.1007/s10107-004-0559-y |
| [39] | Williams, HP, The reformulation of two mixed integer programming problems, Math. Program., 14, 1, 325-331 (1978) · Zbl 0376.90077 · doi:10.1007/BF01588974 |
| [40] | Zheng, X.; Sun, X.; Li, D., Improving the performance of MIQP solvers for quadratic programs with cardinality and minimum threshold constraints: A semidefinite program approach, INFORMS J. Comput., 26, 4, 690-703 (2014) · Zbl 1304.90154 · doi:10.1287/ijoc.2014.0592 |
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.
