Paper Info
Title
A Worst-Case Analysis of Constraint-Based Algorithms for Exact Multi-objective Combinatorial Optimization.
Abstract
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.
Year
DOI
Venue
2017
10.1007/978-3-319-57351-9_16
ADVANCES IN ARTIFICIAL INTELLIGENCE, CANADIAN AI 2017
Field
DocType
Volume
Extremal optimization,Computer science,Quadratic assignment problem,Algorithm,Constraint satisfaction problem,Combinatorial optimization,Combinatorial search,Combinatorial explosion,Optimization problem,Metaheuristic
Conference
10233
ISSN
Citations 
PageRank 
0302-9743
1
0.34
References 
Authors
8
4
Name
Order
Citations
PageRank
Jianmei Guo139022.80
Eric Blais228622.49
Krzysztof Czarnecki36064411.57
Peter Van Beek41612141.30