You are here

A Support-Based Algorithm for the Bi-Objective Pareto Constraint

TitleA Support-Based Algorithm for the Bi-Objective Pareto Constraint
Publication TypeConference Paper
Year of Publication2014
AuthorsHartert, Renaud
EditorSchaus, Pierre
Conference NameAAAI 2014
Publisher In Twenty-Eighth AAAI Conference on Artificial Intelligence
Conference LocationQuebec
KeywordsBi-Objective, Global Constraint, OscaR
Abstract

Bi-Objective Combinatorial Optimization problems are ubiquitous in real-world applications and designing approaches to solve them efficiently is an important research area of Artificial Intelligence. In Constraint Programming, the recently introduced bi-objective Pareto constraint allows one to solve bi-objective combinatorial optimization problems exactly. Using this constraint, every non-dominated solution is col- lected in a single tree-search while pruning sub-trees that cannot lead to a non-dominated solution. This paper introduces a simpler and more efficient filtering algo- rithm for the bi-objective Pareto constraint. The effi- ciency of this algorithm is experimentally confirmed on classical bi-objective benchmarks.