Faculty of Science, Technology and Medicine
Faculty of Law, Economics and Finance
Faculty of Humanities, Education and Social Sciences
Interdisciplinary Centre for Security, Reliability and Trust
Luxembourg Centre for Systems Biomedicine
Luxembourg Centre for Contemporary and Digital History
Luxembourg Centre for European Law
Luxembourg Centre for Socio-Environmental Systems
The Doctoral School in Science and Engineering is happy to invite you to Manuel COMBARRO SIMON’s defence entitled
Exact Multi-objective Algorithms in Constraint Programming
Supervisor: Prof Pascal BOUVRY
Many real-world combinatorial optimization problems involve several potentially conflicting objectives.
When preferences among objectives are not fixed a priori, solving such problems does not lead to a single optimum, but to a set of trade-off solutions known as the Pareto front.
In contrast to mathematical programming and, more recently, Boolean satisfiability (SAT), where many exact methods have been proposed, exact algorithms in constraint programming (CP) specifically designed to compute the full Pareto front remain comparatively limited.
This thesis studies how exact multi-objective algorithms from mathematical programming and SAT can be adapted to CP, and whether they can outperform one of the main state-of-the-art exact methods in CP.
It also proposes a new exact CP algorithm inspired by ideas from mathematical programming and CP-specific techniques.
The thesis first introduces the necessary background on CP, multi-objective optimization, the indicators used to evaluate Pareto-front approximations, and the benchmark problems used throughout the experimental study.
It also introduces the satellite image mosaic selection problem (SIMS), a new multi-objective combinatorial optimization problem from Earth observation, and shows that, beyond optimization itself, its reliable solving process in practice depends on trustworthiness aspects such as data quality, preprocessing, and metadata interoperability, which are only partially addressed by current standards.
The following chapters provide a brief review of the state of the art in exact multi-objective optimization in CP and describe in more detail the state-of-the-art CP algorithm used as the experimental baseline.
The thesis then presents CP implementations of three well-known exact methods from SAT and mathematical programming.
These adaptations show how CP-specific mechanisms, in particular the Pareto global constraint and the lexicographic ordering global constraint, can be integrated into algorithms originally developed outside CP.
Finally, the thesis proposes PAUGMECON, a new exact algorithm built on the well-known $\epsilon$-constraint variant SAUGMECON, which reduces repeated exploration of the objective space through the use of the Pareto global constraint, together with several additional improvements.
An experimental evaluation on four benchmark problems shows that the adapted algorithms and PAUGMECON are competitive with the CP baseline.
In particular, PAUGMECON achieves the best overall performance on three of the four benchmark problems in the bi- and tri-objective settings, including the most challenging ones.
Overall, this thesis shows that adapting exact methods from SAT and mathematical programming to CP is effective, and that combining these ideas with CP-specific propagation mechanisms leads to stronger exact algorithms for multi-objective combinatorial optimization.