AAAI Publications, Twenty-Eighth AAAI Conference on Artificial Intelligence

Font Size: 
A Support-Based Algorithm for the Bi-Objective Pareto Constraint
Renaud Hartert, Pierre Schaus

Last modified: 2014-06-21

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 collected 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 algorithm for the bi-objective Pareto constraint. The efficiency of this algorithm is experimentally confirmed on classical bi-objective benchmarks.

Keywords


Constraint programming, global constraint, bi-objective optimization

Full Text: PDF