TY - GEN
T1 - A worst-case analysis of constraint-based algorithms for exact multi-objective combinatorial optimization
AU - Guo, Jianmei
AU - Blais, Eric
AU - Czarnecki, Krzysztof
AU - Van Beek, Peter
N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - In a multi-objective combinatorial optimization (MOCO) problem, multiple objectives must be optimized simultaneously. In past years, several constraint-based algorithms have been proposed for finding Pareto-optimal solutions to MOCO problems that rely on repeated calls to a constraint solver. Understanding the properties of these algorithms and analyzing their performance is an important problem. Previous work has focused on empirical evaluations on benchmark instances. Such evaluations, while important, have their limitations. Our paper adopts a different, purely theoretical approach, which is based on characterizing the search space into subspaces and analyzing the worst-case performance of a MOCO algorithm in terms of the expected number of calls to the underlying constraint solver. We apply the approach to two important constraint-based MOCO algorithms. Our analysis reveals a deep connection between the search mechanism of a constraint solver and the exploration of the search space of a MOCO problem.
AB - In a multi-objective combinatorial optimization (MOCO) problem, multiple objectives must be optimized simultaneously. In past years, several constraint-based algorithms have been proposed for finding Pareto-optimal solutions to MOCO problems that rely on repeated calls to a constraint solver. Understanding the properties of these algorithms and analyzing their performance is an important problem. Previous work has focused on empirical evaluations on benchmark instances. Such evaluations, while important, have their limitations. Our paper adopts a different, purely theoretical approach, which is based on characterizing the search space into subspaces and analyzing the worst-case performance of a MOCO algorithm in terms of the expected number of calls to the underlying constraint solver. We apply the approach to two important constraint-based MOCO algorithms. Our analysis reveals a deep connection between the search mechanism of a constraint solver and the exploration of the search space of a MOCO problem.
UR - https://www.scopus.com/pages/publications/85019218688
U2 - 10.1007/978-3-319-57351-9_16
DO - 10.1007/978-3-319-57351-9_16
M3 - 会议稿件
AN - SCOPUS:85019218688
SN - 9783319573502
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 117
EP - 128
BT - Advances in Artificial Intelligence - 30th Canadian Conference on Artificial Intelligence, Canadian AI 2017, Proceedings
A2 - Langlais, Philippe
A2 - Mouhoub, Malek
PB - Springer Verlag
T2 - 30th Canadian Conference on Artificial Intelligence, AI 2017
Y2 - 16 May 2017 through 19 May 2017
ER -