Constraint propagation using dominance in interval branch & bound for nonlinear biobjective optimization. (English) Zbl 1403.90612

Summary: Constraint propagation has been widely used in nonlinear single-objective optimization inside interval branch & bound algorithms as an efficient way to discard infeasible and non-optimal regions of the search space. On the other hand, when considering two objective functions, constraint propagation is uncommon. It has mostly been applied in combinatorial problems inside particular methods. The difficulty is in the exploitation of dominance relations in order to discard the so-called non-Pareto optimal solutions inside a decision domain, which complicates the design of complete and efficient constraint propagation methods exploiting dominance relations. In this paper, we present an interval branch & bound algorithm which integrates dominance contractors, constraint propagation mechanisms that exploit an upper bound set using dominance relations. This method discards from the decision space values yielding solutions dominated by some solutions from the upper bound set. The effectiveness of the approach is shown on a sample of benchmark problems.


90C29 Multi-objective and goal programming
90C30 Nonlinear programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
65K05 Numerical mathematical programming methods
Full Text: DOI


[1] Araya, I.; Trombettoni, G.; Neveu, B., Exploiting monotonicity in interval constraint propagation, Proceedings of the association for the advancement of artificial intelligence conference, Aaai, (2010)
[2] Barichard, V.; Hao, J., A population and interval constraint propagation algorithm, Lncs, 88-101, (2003), Springer · Zbl 1036.90565
[3] Benhamou, F.; Goualard, F.; Granvilliers, L.; Puget, J.-F., Revising hull and box consistency, Proceedings of the international conference on logic programming, 230-244, (1999), MIT press
[4] Benhamou, F.; Granvilliers, L., Chapter 16 - continuous and interval constraints, (Francesca Rossi, P.v. B.; Walsh, T., Handbook of constraint programming, Vol. 2, (2006), Elsevier), 571-603
[5] Benhamou, F.; McAllister, D.; Hentenryck, P. V., CLP(intervals) revisited, International symposium on logic programming, 124-138, (1994)
[6] Coello, C. A.C.; Lamont, G. B.; Van Veldhuizen, D. A., Evolutionary algorithms for solving multi-objective problems (genetic and evolutionary computation), (2006), Springer-Verlag New York, Inc Secaucus, NJ, USA
[7] Collavizza, H.; Delobel, F.; Rueher, M., Comparing partial consistencies, Reliable Computing, 5, 3, 213-228, (1999) · Zbl 1130.65310
[8] Das, I.; Dennis, J., Normal-boundary intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems, SIAM Journal on Optimization, 8, 3, 631-657, (1998) · Zbl 0911.90287
[9] Deb, K.; Pratap, A.; Meyarivan, T., Constrained test problems for multi-objective evolutionary optimization, (Zitzler, E.; Thiele, L.; Deb, K.; Coello Coello, C. A.; Corne, D., Evolutionary multi-criterion optimization, Lecture notes in computer science, Vol. 1993, (2001), Springer Berlin Heidelberg), 284-298
[10] Ehrgott, M., Multicriteria optimization, (2005), Springer · Zbl 1132.90001
[11] Ehrgott, M.; Gandibleux, X., Bound sets for biobjective combinatorial optimization problems, Computers and Operations Research, 34, 9, 2674-2694, (2007) · Zbl 1141.90509
[12] Fernández, J.; Tóth, B., Obtaining an outer approximation of the efficient set of nonlinear biobjective problems, Journal of Global Optimization, 38, 2, 315-331, (2007) · Zbl 1172.90482
[13] Fernández, J.; Tóth, B., Obtaining the efficient set of nonlinear biobjective optimization problems via interval branch-and-bound methods, Computational Optimization and Applications, 42, 3, 393-419, (2009) · Zbl 1211.90208
[14] Gavanelli, M., An algorithm for multi-criteria optimization in csps, European conference on artificial intelligence, (2002), IOS Press
[15] Goldsztejn, A.; Domes, F.; Chevalier, B., First order rejection tests for multiple-objective optimization, Journal of Global Optimization, 58, 4, 653-672, (2014) · Zbl 1301.90082
[16] Goualard, F., GAOL: not just another interval arithmetic library, LINA., (2006), https://sourceforge.net/projects/gaol/
[17] Granvilliers, L.; Benhamou, F., Algorithm 852: realpaver: an interval solver using constraint satisfaction techniques, ACM Transactions Mathematical Software, 32, 1, 138-156, (2006) · Zbl 1346.65020
[18] Hansen, E.; Walster, G. W., Global optimization using interval analysis - revised and expanded, (2003), CRC Press
[19] Hartert, R.; Schaus, P., A support-based algorithm for the bi-objective Pareto constraint, Proceedings of the Aaai conference on artificial intelligence, (2014)
[20] Jaulin, L.; Kieffer, M.; Didrit, O.; Walter, E., Applied interval analysis with examples in parameter and state estimation, robust control and robotics, (2001), Springer-Verlag · Zbl 1023.65037
[21] Kearfott, R. B., Interval computations: introduction, uses, and resources, Euromath Bulletin, 2, 1, 95-112, (1996)
[22] Kearfott, R. B., Rigorous global search: Continuous problems, (1996), Kluwer Academic Publishers · Zbl 0876.90082
[23] Kim, I. Y.; de Weck, O. L., Adaptive weighted-sum method for bi-objective optimization: Pareto front generation, Structural and Multidisciplinary Optimization, 29, 2, 149-158, (2005)
[24] Klamroth, K.; Lacour, R.; Vanderpooten, D., On the representation of the search region in multi-objective optimization, European Journal of Operational Research, 245, 3, 767-778, (2015) · Zbl 1346.90739
[25] Kubica, B. J.; Woźniak, A., Interval methods for computing the Pareto-front of a multicriterial problem, Proceedings of the international conference on parallel processing and applied mathematics. PPAM’07, 1382-1391, (2008)
[26] Kubica, B. J.; Woźniak, A., Using the second-order information in Pareto-set computations of a multi-criteria problem, (Jónasson, K., Applied parallel and scientific computing. LNCS, Vol. 7134, (2012), Springer), 137-147
[27] Kubica, B. J.; Woźniak, A., Tuning the interval algorithm for seeking Pareto sets of multi-criteria problems, (Manninen, P.; ster, P., Applied parallel and scientific computing. LNCS, Vol. 7782, (2013), Springer), 504-517
[28] Lebbah, Y.; Michel, C.; Rueher, M., An efficient and safe framework for solving optimization problems, Journal of Computational and Applied Mathematics, 199, 2, 372-377, (2007) · Zbl 1108.65065
[29] Lhomme, O., Consistency techniques for numeric csps, Proceedings of the international joint conference on artificial intelligence, 232-238, (1993)
[30] Lhomme, O., Quick shaving, Proceedings of the Aaai conference on artificial intelligence, 411-415, (2005), AAAI Press
[31] Martin, B., Rigorous algorithms for nonlinear biobjective optimization, (2014), Université de Nantes, (Ph.D. thesis)
[32] Martin, B.; Goldsztejn, A.; Granvilliers, L.; Jermann, C., On continuation methods for non-linear bi-objective optimization: towards a certified interval-based approach, Journal of Global Optimization, 64, 1, 3-16, (2016) · Zbl 1332.90251
[33] Miettinen, K., Nonlinear multiobjective optimization, Int. Series in Operations Research and Management Science, Vol. 12, (1999), Kluwer · Zbl 0949.90082
[34] Moore, R., Interval analysis, (1966), Prentice-Hall · Zbl 0176.13301
[35] Neumaier, A., Interval methods for systems of equations, (1991), Cambridge University Press
[36] Neumaier, A., Second-order sufficient optimality conditions for local and global nonlinear programming, Journal of Global Optimization, 9, 2, 141-151, (1996) · Zbl 0868.90112
[37] Neumaier, A., Complete search in continuous global optimization and constraint satisfaction, Acta Numerica, 13, 271-369, (2004) · Zbl 1113.90124
[38] Neveu, B.; Trombettoni, G.; Araya, I., Adaptive constructive interval disjunction: algorithms and experiments, Constraints, 20, 7, 452-467, (2015) · Zbl 1329.90152
[39] Osyczka, A.; Kundu, S., A new method to solve generalized multicriteria optimization problems using the simple genetic algorithm, Structural Optimization, 10, 2, 94-99, (1995)
[40] Przybylski, A.; Gandibleux, X.; Ehrgott, M., A two phase method for multi-objective integer programming and its application to the assignment problem with three objectives, Discrete Optimization, 7, 3, 149-165, (2010) · Zbl 1241.90138
[41] Reyes-Sierra, M.; Coello, C. A.C., Multi-objective particle swarm optimizers: A survey of the state-of-the-art, International Journal of Computational Intelligence Research, 2, 3, 287-308, (2006)
[42] Ruetsch, G., An interval algorithm for multi-objective optimization, Structural and Multidisciplinary Optimization, 30, 27-37, (2005) · Zbl 1243.90205
[43] Rump, S., A note on epsilon-inflation, Reliable Computing, 4, 371-375, (1998) · Zbl 0920.65031
[44] Schütze, O.; Dell’Aere, A.; Dellnitz, M., On continuation methods for the numerical treatment of multi-objective optimization problems, (et al., J. B., Practical approaches to multi-objective optimization, (2005))
[45] Tóth, B.; Fernández, J., Interval methods for single and bi-objective optimization problems-applied to competitive facility location problems, (2010), Lambert Academic Publishing Saarbrücken
[46] Trombettoni, G.; Araya, I.; Neveu, B.; Chabert, G., Inner regions and interval linearizations for global optimization, Proceedings of the Aaai conference on artificial intelligence, (2011)
[47] Trombettoni, G.; Chabert, G., Constructive interval disjunction, Proceedings of the international conference on principles and practice of constraint programming, LNCS, Vol. 4741, 635-650, (2007), Springer · Zbl 1145.68530
[48] Van Hentenryck, P.; Michel, L.; Deville, Y., Numerica: A modeling language for global optimization, (1997), MIT press
[49] Villa, C.; Lozinguez, E.; Labayrade, R., Multi-objective optimization under uncertain objectives: application to engineering design problem, (Purshouse, R. C.; Fleming, P. J.; Fonseca, C. M.; Greco, S.; Shaw, J., Proceedings of the seventh international conference on evolutionary multi-criterion optimization, emo 2013,, (2013), Springer Berlin Heidelberg), 796-810
[50] Zhang, Q.; Zhou, A.; Zhao, S.; Suganthan, P. N.; Liu, W.; Tiwari, S., Multiobjective optimization test instances for the cec 2009 special session and competition, special session on performance assessment of multi-objective optimization algorithms, technical report, Vol. 264, (2008), University of Essex, Colchester, UK and Nanyang technological University, Singapore
[51] Zhang, Z., Immune optimization algorithm for constrained nonlinear multiobjective optimization problems, Applied Soft Computing, 7, 3, 840-857, (2007)
[52] Zitzler, E.; Thiele, L.; Laumanns, M.; Fonseca, C.; da Fonseca, V., Performance assessment of multiobjective optimizers: an analysis and review, IEEE Transactions on Evolutionary Computation, 7, 2, 117-132, (2003)
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.