Nonlinear biobjective optimization: improvements to interval branch & bound algorithms. (English) Zbl 1429.90066

Araya, Ignacio; Campusano, Jose; Aliquintui, Damir

J. Glob. Optim. 75, No. 1, 91-110 (2019).

Summary: Interval based solvers are commonly used for solving single-objective nonlinear optimization problems. Their reliability and increasing performance make them useful when proofs of infeasibility and/or certification of solutions are a must. On the other hand, there exist only a few approaches dealing with nonlinear optimization problems, when they consider multiple objectives. In this paper, we propose a new interval branch & bound algorithm for solving nonlinear constrained biobjective optimization problems. Although the general strategy is based on other works, we propose some improvements related to the termination criteria, node selection, upperbounding and discarding boxes using the non-dominated set. Most of these techniques use and/or adapt components of IbexOpt, a state-of-the-art interval-based single-objective optimization algorithm. The code of our plugin can be found in our git repository (https://github.com/INFPUCV/ibex-lib/tree/master/plugins/optim-mop).

MSC:

90C29	Multi-objective and goal programming
90C57	Polyhedral combinatorics, branch-and-bound, branch-and-cut

Keywords:

interval methods; branch & bound; multiobjective optimization

Software:

ibexMop; FEMOEA; GitHub

References:

[1]	Marler, R.T., Arora, J.S.: Survey of multi-objective optimization methods for engineering. Struct. Multidiscipl. Optim. 26(6), 369-395 (2004) · Zbl 1243.90199 · doi:10.1007/s00158-003-0368-6
[2]	Deb, K.: Multi-objective optimization. In: Search Methodologies. Springer, pp. 403-449 (2014)
[3]	Przybylski, A., Gandibleux, X.: Multi-objective branch and bound. Eur. J. Oper. Res. 260(3), 856-872 (2017) · Zbl 1403.90615 · doi:10.1016/j.ejor.2017.01.032
[4]	Redondo, J.L., Fernández, J., Ortigosa, P.M.: FEMOEA: a fast and efficient multi-objective evolutionary algorithm. Math. Methods Oper. Res. 85(1), 113-135 (2017) · Zbl 1364.90306 · doi:10.1007/s00186-016-0560-2
[5]	Coello, C.A.C., Lamont, G.B., Van Veldhuizen, D.A., et al.: Evolutionary Algorithms for Solving Multi-objective Problems, vol. 5. Springer, Berlin (2007) · Zbl 1142.90029
[6]	Ruetsch, G.: An interval algorithm for multi-objective optimization. Struct. Multidiscip. Optim. 30(1), 27-37 (2005) · Zbl 1243.90205 · doi:10.1007/s00158-004-0496-7
[7]	Fernández, J., Tóth, B.: Obtaining an outer approximation of the efficient set of nonlinear biobjective problems. J. Glob. Optim. 38(2), 315-331 (2007) · Zbl 1172.90482 · doi:10.1007/s10898-006-9132-y
[8]	Fernández, J., Tóth, B.: Obtaining the efficient set of nonlinear biobjective optimization problems via interval branch-and-bound methods. Comput. Optim. Appl. 42(3), 393-419 (2009) · Zbl 1211.90208 · doi:10.1007/s10589-007-9135-8
[9]	Kubica, B. J., Woźniak, A.: Tuning the interval algorithm for seeking pareto sets of multi-criteria problems. In: International Workshop on Applied Parallel Computing. Springer, pp. 504-517 (2012)
[10]	Martin, B., Goldsztejn, A., Granvilliers, L., Jermann, C.: On continuation methods for non-linear bi-objective optimization: towards a certified interval-based approach. J. Glob. Optim. 64(1), 3-16 (2016) · Zbl 1332.90251 · doi:10.1007/s10898-014-0201-3
[11]	Martin, B., Goldsztejn, A., Granvilliers, L., Jermann, C.: Constraint propagation using dominance in interval branch & bound for nonlinear biobjective optimization. Eur. J. Oper. Res. 260(3), 934-948 (2017) · Zbl 1403.90612 · doi:10.1016/j.ejor.2016.05.045
[12]	Niebling, J., Eichfelder, G.: A branch-and-bound based algorithm for nonconvex multiobjective optimization. Preprint-Series of the Institute for Mathematics (2018) · Zbl 1414.90288
[13]	Goldsztejn, A., Domes, F., Chevalier, B.: First order rejection tests for multiple-objective optimization. J. Glob. Optim. 58(4), 653-672 (2014) · Zbl 1301.90082 · doi:10.1007/s10898-013-0066-x
[14]	Araya, I., Trombettoni, G., Neveu, B., Chabert, G.: Upper bounding in inner regions for global optimization under inequality constraints. J. Glob. Optim. 60(2), 145-164 (2014) · Zbl 1312.90057 · doi:10.1007/s10898-014-0145-7
[15]	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)
[16]	Araya, I., Neveu, B.: lsmear: a variable selection strategy for interval branch and bound solvers. J. Glob. Optim. 71(3), 483-500 (2018) · Zbl 1402.90123 · doi:10.1007/s10898-017-0569-y
[17]	Benhamou, F., Goualard, F., Granvilliers, L., Puget, J.-F.: Revising hull and box consistency. In: International Conference on Logic Programming, Citeseer (1999)
[18]	Neveu, B., Trombettoni, G., et al.: Adaptive constructive interval disjunction. In: International Conference on Tools with Artificial Intelligence (ICTAI), pp. 900-906 (2013)
[19]	Ninin, J., Messine, F., Hansen, P.: A reliable affine relaxation method for global optimization. 4OR 13(3), 247-277 (2015) · Zbl 1320.90065 · doi:10.1007/s10288-014-0269-0
[20]	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. Springer, pp. 1-16 (2012) · Zbl 1241.68008
[21]	Martin, B.: Rigorous algorithms for nonlinear biobjective optimization. Ph.D. dissertation, Université de Nantes (2014)
[22]	Tóth, B., Fernández, J.: Interval Methods for Single and Bi-objective Optimization Problems-Applied to Competitive Facility Location Problems. Lambert Academic Publishing, Saarbrücken (2010)
[23]	Chabert, G., Jaulin, L.: Contractor programming. Artif. Intell. 173, 1079-1100 (2009) · Zbl 1191.68628 · doi:10.1016/j.artint.2009.03.002
[24]	Trombettoni, G., Chabert, G.: Constructive interval disjunction. In: Principles and Practice of Constraint Programming (CP 2007). Springer, pp. 635-650 (2007) · Zbl 1145.68530
[25]	Csendes, T., Ratz, D.: Subdivision direction selection in interval methods for global optimization. SIAM J. Numer. Anal. 34(3), 922-938 (1997) · Zbl 0873.65063 · doi:10.1137/S0036142995281528
[26]	Moore, R.E.: Interval Analysis. Prentice-Hall, Englewood Cliffs, NJ (1966) · Zbl 0176.13301
[27]	Zitzler, E., Thiele, L.: Multiobjective optimization using evolutionary algorithms: a comparative case study. In: International Conference on Parallel Problem Solving from Nature. Springer, pp. 292-301 (1998)
[28]	Neveu, B., Trombettoni, G., Araya, I.: Node selection strategies in interval branch and bound algorithms. J. Glob. Optim. 64(2), 289-304 (2016) · Zbl 1339.90268 · doi:10.1007/s10898-015-0375-3