×
Araya, Ignacio; Aliquintui, Damir; Ardiles, Franco; Lobo, Braulio

Nonlinear biobjective optimization: improving the upper envelope using feasible line segments. (English) Zbl 1465.90090

J. Glob. Optim. 79, No. 2, 503-520 (2021).
Summary: In this work, we propose a segment-based representation for the upper bound of the non-dominated set in interval branch & bound solvers for biobjective non linear optimization. We ensure that every point over the upper line segments is dominated by at least one point in the feasible objective region. Segments are generated by linear envelopes of the image of feasible line segments. Finally, we show that the segment-based representation together with methods for generating upper line segments allows us to converge more quickly to the desired precision of the whole strategy. The code of our solver 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:

GitHub; ibexMop
PDF BibTeX XML Cite
\textit{I. Araya} et al., J. Glob. Optim. 79, No. 2, 503--520 (2021; Zbl 1465.90090)
Full Text: DOI

References:

[1] Deb, K.: Multi-objective evolutionary algorithms. In: Kacprzyk J., Pedrycz W. (eds.) Springer Handbook of Computational Intelligence. Springer Handbooks. Springer, Berlin, Heidelberg (2015) · Zbl 0970.90091
[2] Miettinen, K., Nonlinear Multiobjective Optimization (2012), Berlin: Springer, Berlin · Zbl 1282.90166
[3] Collette, Y.; Siarry, P., Multiobjective Optimization: Principles and Case Studies (2013), Heidelberg: Springer, Heidelberg · Zbl 1103.90088
[4] Evtushenko, YG; Posypkin, MA, Nonuniform covering method as applied to multicriteria optimization problems with guaranteed accuracy, Comput. Math. Math. Phys., 53, 2, 144-157 (2013) · Zbl 1274.90344
[5] Žilinskas, A.; Žilinskas, J., Adaptation of a one-step worst-case optimal univariate algorithm of bi-objective Lipschitz optimization to multidimensional problems, Commun. Nonlinear Sci. Numer. Simul., 21, 1-3, 89-98 (2015) · Zbl 1329.90134
[6] Pardalos, PM; Žilinskas, A.; Žilinskas, J., Non-convex Multi-objective Optimization (2017), New York: Springer, New York · Zbl 1372.90004
[7] Ruetsch, G., An interval algorithm for multi-objective optimization, Struct. Multidiscipl. Optim., 30, 1, 27-37 (2005) · Zbl 1243.90205
[8] 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
[9] 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
[10] Kubica, B.J., Woźniak, A.: Tuning the interval algorithm for seeking Pareto sets of multi-criteria problems. In: Manninen, P., Öster, P. (eds.) International Workshop on Applied Parallel Computing, pp. 504-517. Springer, New York (2012)
[11] 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
[12] 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
[13] Niebling, J., Eichfelder, G.: A branch-and-bound based algorithm for nonconvex multiobjective optimization. SIAM J. Optim. 29(1), 794-821 (2019) · Zbl 1414.90288
[14] Araya, I.; Campusano, J.; Aliquintui, D., Nonlinear biobjective optimization: improvements to interval branch & bound algorithms, J. Glob. Optim., 75, 1, 91-110 (2019) · Zbl 1429.90066
[15] 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
[16] Hansen, E.; Walster, GW, Global Optimization using Interval Analysis: Revised and Expanded (2003), Boca Raton: CRC Press, Boca Raton
[17] Jaulin, L.; Kieffer, M.; Didrit, O.; Walter, E., Applied Interval Analysis (2001), Berlin: Springer, Berlin
[18] Kutateladze, S., Convex e-programming, Sov. Math. Dokl, 20, 2, 391-393 (1979) · Zbl 0425.49027
[19] Kahan, W., IEEE standard 754 for binary floating-point arithmetic, Lect. Notes Status IEEE, 754, 94720-1776, 11 (1996)
[20] 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
[21] Araya, I., Trombettoni, G., Neveu, B.: A contractor based on convex interval taylor. In: Beldiceanu, N., Jussien N., Pinson, É. (eds.) Integration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems, pp. 1-16. Springer, New York (2012)
[22] Hladík, M., Horáček, J.: Interval linear programming techniques in constraint programming and global optimization. In: Ceberio, M., Kreinovich, V. (eds.) Constraint Programming and Decision Making, pp. 47-59. Springer, New York (2014)
[23] Lebbah, Y.; Michel, C.; Rueher, M.; Daney, D.; Merlet, J., Efficient and safe global constraints for handling numerical constraint systems, SIAM J. Numer. Anal., 42, 5, 2076-2097 (2005) · Zbl 1082.65051
[24] Ninin, J.; Messine, F.; Hansen, P., A reliable affine relaxation method for global optimization, 4OR, 13, 3, 247-277 (2015) · Zbl 1320.90065
[25] Jaulin, L., Reliable minimax parameter estimation, Reliab. Comput., 7, 3, 231-246 (2001) · Zbl 0987.65011
[26] Spielman, DA; Teng, S-H, Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, J. ACM (JACM), 51, 3, 385-463 (2004) · Zbl 1192.90120
[27] Chabert, G.; Jaulin, L., Contractor programming, Artif. Intell., 173, 1079-1100 (2009) · Zbl 1191.68628
[28] Benhamou, F., Goualard, F., Granvilliers, L., Puget, J.-F.: Revising hull and box consistency. In: Int. Conf. on Logic Programming. Citeseer, Las Cruces (1999)
[29] Trombettoni, G., Chabert, G.: Constructive interval disjunction. In: Bessière, C. (ed.) Principles and Practice of Constraint Programming (CP 2007), pp. 635-650. Springer, New York (2007)
[30] 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
[31] Moore, R.: Interval Analysis. Prentice-Hall, Englewood Cliffs (1966) · Zbl 0176.13301
[32] 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
[33] Wilcoxon, F.; Katti, S.; Wilcox, RA, Critical values and probability levels for the Wilcoxon rank sum test and the Wilcoxon signed rank test, Sel. Tables Math. Stat., 1, 171-259 (1970) · Zbl 0121.36201
[34] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Progr., 91, 2, 201-213 (2002) · Zbl 1049.90004
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.