Skip to Main content Skip to Navigation
Conference papers

Pareto-based Soft Arc Consistency for Multi-objective Valued CSPs

Abstract : A valued constraint satisfaction problem (VCSP) is a soft constraint framework that can formalize a wide range of applications related to Combinatorial Optimization and Artificial Intelligence. Most researchers have focused on the development of algorithms for solving mono-objective problems. However, many real-world satisfaction/optimization problems involve multiple objectives that should be considered separately and satisfied/optimized simultaneously. Solving a Multi-Objective Optimization Problem (MOP) consists of finding the set of all non-dominated solutions, known as the Pareto Front. In this paper, we introduce multi-objective valued constraint satisfaction problem (MO-VCSP), that is a VCSP involving multiple objectives, and we extend soft local arc consistency methods, which are widely used in solving Mono-Objective VCSP, in order to deal with the multi-objective case. Also, we present multi-objective enforcing algorithms of such soft local arc consistencies taking into acco unt the Pareto principle. The new Pareto-based soft arc consistency (P-SAC) algorithms compute a Lower Bound Set of the efficient frontier. As a consequence, P-SAC can be integrated into a Multi-Objective Branch and Bound (MO-BnB) algorithm in order to ensure its pruning efficiency.
Complete list of metadata
Contributor : Limeme BEN ALI Connect in order to contact the contributor
Submitted on : Friday, June 25, 2021 - 10:35:09 AM
Last modification on : Friday, March 4, 2022 - 4:04:01 PM


Distributed under a Creative Commons Attribution - NonCommercial - NoDerivatives 4.0 International License

Links full text




Limeme Ben Ali, Maher Helaoui, Wady Naanaa. Pareto-based Soft Arc Consistency for Multi-objective Valued CSPs. 11th International Conference on Agents and Artificial Intelligence, Feb 2019, Prague, Czech Republic. pp.294-305, ⟨10.5220/0007401802940305⟩. ⟨hal-03270734⟩



Record views