×

zbMATH — the first resource for mathematics

On handling indicator constraints in mixed integer programming. (English) Zbl 1357.90094
Summary: Mixed integer programming (MIP) is commonly used to model indicator constraints, i.e., constraints that either hold or are relaxed depending on the value of a binary variable. Unfortunately, those models tend to lead to weak continuous relaxations and turn out to be unsolvable in practice; this is what happens, for e.g., in the case of classification problems with ramp loss functions that represent an important application in this context. In this paper we show the computational evidence that a relevant class of these classification instances can be solved far more efficiently if a nonlinear, nonconvex reformulation of the indicator constraints is used instead of the linear one. Inspired by this empirical and surprising observation, we show that aggressive bound tightening is the crucial ingredient for solving this class of instances, and we devise a pair of computationally effective algorithmic approaches that exploit it within MIP. One of these methods is currently part of the arsenal of IBM-Cplex  since version 12.6.1. More generally, we argue that aggressive bound tightening is often overlooked in MIP, while it represents a significant building block for enhancing MIP technology when indicator constraints and disjunctive terms are present.

MSC:
90C11 Mixed integer programming
90C20 Quadratic programming
Software:
Bonmin; Cbc; CPLEX; MIPLIB; XPRESS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andersen, E; Andersen, K, Presolving in linear programming, Math. Program., 71, 221-245, (1995) · Zbl 0846.90068
[2] Balas, E, Disjunctive programming, Ann. Discret. Math., 5, 3-51, (1979) · Zbl 0409.90061
[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
[4] Bonami, P; Biegler, LT; Conn, AR; Cornuéjols, G; Grossmann, IE; Laird, CD; Lee, J; Lodi, A; Margot, F; Sawaya, N; Wächter, A, An algorithmic framework for convex mixed integer nonlinear programs, Discret. Optim., 5, 186-2004, (2008) · Zbl 1151.90028
[5] Bonami, P; Kilinc, M; Linderoth, J; Lee, J (ed.); Leyffer, S (ed.), Algorithms and software for convex mixed integer nonlinear programs, 1-40, (2012), Berlin · Zbl 1242.90121
[6] Bonami, P; Lodi, A; Tramontani, A; Wiese, S, On mathematical programming with indicator constraints, Math. Program., 151, 191-223, (2015) · Zbl 1328.90086
[7] Bonmin, v. 1.7.4. https://projects.coin-or.org/Bonmin
[8] Brooks, JP, Support vector machines with the ramp loss and the hard margin loss, Oper. Res., 59, 467-479, (2011) · Zbl 1228.90057
[9] Carrizosa, E; Romero Morales, D, Supervised classification and mathematical optimization, Comput. Oper. Res., 40, 150-165, (2013) · Zbl 1349.68135
[10] Cbc, v. 2.9. https://projects.coin-or.org/Cbc
[11] Ceria, S; Soares, J, Convex programming for disjunctive convex optimization, Math. Program., 86, 595-614, (1999) · Zbl 0954.90049
[12] Collobert, R., Sinz, F., Weston, J., Bottou, L.: Trading convexity for scalability. In: Proceedings of the 23rd International Conference on Machine Learning, pp. 201-208 (2006) · Zbl 1349.68135
[13] Couenne, v. branch/CouenneClassifier, r1046. https://projects.coin-or.org/Couenne · Zbl 1328.90086
[14] Cristianini, N., Shawe-Taylor, J.: An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods. Cambridge University Press, Cambridge (2000) · Zbl 0994.68074
[15] Davis, E, Constraint propagation with interval labels, Artif. Intell., 32, 281-331, (1987) · Zbl 0642.68176
[16] Duran, MA; Grossmann, I, An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Math. Program., 36, 307-339, (1986) · Zbl 0619.90052
[17] FICO Xpress Optimization Suite, v. 7.8. http://www.fico.com/xpress · Zbl 1151.90028
[18] Fischetti, M; Monaci, M, Exploiting erraticism in search, Oper. Res., 62, 114-122, (2014) · Zbl 1291.90148
[19] Grossmann, IE; Trespalacios, F, Systematic modeling of discrete-continuous optimization models through generalized disjunctive programming, AIChE J., 59, 3276-3295, (2013)
[20] Gurobi, v. 6.0.2. http://www.gurobi.com · Zbl 1052.62095
[21] IBM-Cplex, v. 12.6.1. http://www.ibm.com/software/products/en/ibmilogcpleoptistud
[22] Ipopt, v. 3.9.2. http://projects.coin-or.org/Ipopt · Zbl 0954.90049
[23] Koch, T; Achterberg, T; Andersen, E; Bastert, O; Berthold, T; Bixby, RE; Danna, E; Gamrath, G; Gleixner, AM; Heinz, S; Lodi, A; Mittelmann, H; Ralphs, T; Salvagnin, D; Steffy, DE; Wolter, K, Miplib 2010, Math. Program. Comput., 3, 103-163, (2011)
[24] Lodi, A; Tramontani, A; Topaloglu, H (ed.), Performance variability in mixed-integer programming, 1-12, (2013), Catonsville
[25] McCormick, GP, Computability of global solutions to factorable nonconvex programs: part I—convex underestimating problems, Math. Program., 10, 147-175, (1976) · Zbl 0349.90100
[26] Messine, F, Deterministic global optimization using interval constraint propagation techniques, RAIRO-RO, 38, 277-294, (2004) · Zbl 1114.90156
[27] Quesada, I; Grossmann, IE, An LP/NLP based branch-and-bound algorithm for convex MINLP optimization problems, Comput. Chem. Eng., 16, 937-947, (1992)
[28] Savelsbergh, MWP, Preprocessing and probing techniques for mixed integer programming problems, ORSA J. Comput., 6, 445-454, (1994) · Zbl 0814.90093
[29] Shen, X; Tseng, GC; Zhang, X; Wong, WH, On \(ψ \)-learning, J. Am. Stat. Assoc., 98, 724-734, (2003) · Zbl 1052.62095
[30] Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer Academic Publishers, Boston (2002) · Zbl 1031.90022
[31] Wu, X; Kumar, V; Ross Quinlan, J; Ghosh, J; Yang, Q; Motoda, H; McLachlan, GJ; Ng, A; Liu, B; Yu, PS; Zhou, Z-H; Steinbach, M; Hand, DJ; Steinberg, D, Top 10 algorithms in data mining, Knowl. Inf. Syst., 14, 1-37, (2007)
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.