lsmear: a variable selection strategy for interval branch and bound solvers. (English) Zbl 1402.90123

Summary: Smear-based variable selection strategies are well-known and commonly used by branch-and-prune interval-based solvers. They estimate the impact of the variables on each constraint of the system by using the partial derivatives and the sizes of the variable domains. Then they aggregate these values, in some way, to estimate the impact of each variable on the whole system. The variable with the greatest impact is then selected. A problem of these strategies is that they, generally, consider all constraints equally important. In this work, we propose a new variable selection strategy which first weights the constraints by using the optimal Lagrangian multipliers of a linearization of the original problem. Then, the impact of the variables is computed with a typical smear-based function but taking into account the weights of the constraints. The strategy isg tested on a set of well-known benchmark instances outperforming significantly the classical variable selection strategies.


90C26 Nonconvex programming, global optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Full Text: DOI


[1] Araya, I., Reyes, V., Oreallana, C.: More smear-based variable selection heuristics for NCSPs. In: International Conference on Tools with Artificial Intelligence (ICTAI 2013). IEEE, pp. 1004-1011 (2013)
[2] Csendes, T; Ratz, D, Subdivision direction selection in interval methods for global optimization, SIAM J. Numer. Anal., 34, 922-938, (1997) · Zbl 0873.65063
[3] Granvilliers, L.: Adaptive bisection of numerical CSPs. In: Principles and Practice of Constraint Programming, pp. 290-298. Springer, New York (2012) · Zbl 1191.68628
[4] Kearfott, RB; Novoa, M, Algorithm 681: INTBIS, a portable interval Newton/bisection package, ACM Trans. Math. Softw. (TOMS), 16, 152-157, (1990) · Zbl 0900.65152
[5] Lagouanelle, J-L; Soubry, G, Optimal multisections in interval branch-and-bound methods of global optimization, J. Glob. Optim., 30, 23-38, (2004) · Zbl 1136.90521
[6] Trombettoni, G., Araya, I., Neveu, B., Chabert, G.: Inner regions and interval linearizations for global optimization. In: AAAI Conference on Artificial Intelligence, pp. 99-104 (2011)
[7] Trombettoni, G; Chabert, G, Constructive interval disjunction, Princ. Pract. Constr. Program., 2007, 635-650, (2007) · Zbl 1145.68530
[8] Moore, R.: Interval analysis, vol. 60. Prentice-Hall Englewood Cliffs, New Jersey (1966) · Zbl 1108.65065
[9] Ratz, D.: Automatische ergebnisverikation bei globalen optimierungsproblemen. Ph.D. dissertation, Universität Karlsruhe (1992) · Zbl 0831.65068
[10] Hansen, E., Walster, G.W.: Global Optimization Using Interval Analysis: Revised and Expanded, vol. 264. CRC Press, Boca Raton (2003)
[11] Tawarmalani, M; Sahinidis, NV, Global optimization of mixed-integer nonlinear programs: a theoretical and computational study, Math. Program., 99, 563-591, (2004) · Zbl 1062.90041
[12] Lebbah, Y, Icos: a branch and bound based solver for rigorous global optimization, Optim. Methods Softw., 24, 709-726, (2009) · Zbl 1179.90265
[13] Ninin, J; Messine, F; Hansen, P, A reliable affine relaxation method for global optimization, 4OR, 13, 247-277, (2015) · Zbl 1320.90065
[14] Araya, I., Trombettoni, G., Neveu, B., Chabert, G.: Upper bounding in inner regions for global optimization under inequality constraints. J. Optim. Glob. (2014). doi:10.1007/s10898-014-0145-7 · Zbl 1312.90057
[15] Neveu, B; Trombettoni, G; Araya, I, Node selection strategies in interval branch and bound algorithms, J. Glob. Optim., 64, 289-304, (2016) · Zbl 1339.90268
[16] Benhamou, F., Goualard, F., Granvilliers, L., Puget, J.-F.: Revising hull and box consistency. In: International Conference on Logic Programming, Citeseer (1999) · Zbl 1179.90265
[17] Araya, I., Trombettoni, G., Neveu, B., et al.: Exploiting monotonicity in interval constraint propagation. In: AAAI (2010) · Zbl 1062.90041
[18] Lhomme, O.: Consistency techniques for numeric CSPs. In: IJCAI. Citeseer, pp. 232-238 (1993)
[19] Neveu, B., Trombettoni, G., et al.: Adaptive constructive interval disjunction. In: International Conference on Tools with Artificial Intelligence (ICTAI), pp. 900-906 (2013)
[20] Lebbah, Y; Michel, C; Rueher, M, An efficient and safe framework for solving optimization problems, J. Comput. Appl. Math., 199, 372-377, (2007) · Zbl 1108.65065
[21] Baharev, A; Achterberg, T; Rév, E, Computation of an extractive distillation column with affine arithmetic, AIChE J., 55, 1695-1704, (2009)
[22] Araya, I., Trombettoni, G., Neveu, B.: A contractor based on convex interval taylor. In: Integration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems, pp. 1-16. Springer, New York (2012)
[23] Goldsztejn, A., Lebbah, Y., Michel, C., Rueher, M.: Revisiting the upper bounding process in a safe branch and bound algorithm. In: Principles and Practice of Constraint Programming (CP), pp. 598-602. Springer, New York (2008) · Zbl 1136.90521
[24] Wunderling, R.: Soplex: The sequential object-oriented simplex class library. http://www.zib.de/Optimization/Software/Soplex/soplex.php (1997) · Zbl 0900.65152
[25] Chabert, G; Jaulin, L, Contractor programming, Artif. Intell., 173, 1079-1100, (2009) · Zbl 1191.68628
[26] Tawarmalani, M; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249, (2005) · Zbl 1099.90047
[27] Misener, R., Floudas, C.A.: ANTIGONE: Algorithms for continuous/integer global optimization of nonlinear equations. J. Glob. Optim. 59(2), 503-526 (2014) · Zbl 1301.90063
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.