Stratification for Constraint-Based Multi-Objective Combinatorial Optimization

Stratification for Constraint-Based Multi-Objective Combinatorial Optimization

Miguel Terra-Neves, Inês Lynce, Vasco Manquinho

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 1376-1382. https://doi.org/10.24963/ijcai.2018/191

New constraint-based algorithms have been recently proposed to solve Multi-Objective Combinatorial Optimization (MOCO) problems. These new methods are based on Minimal Correction Subsets (MCSs) or P-minimal models and have shown to be successful at solving MOCO instances when the constraint set is hard to satisfy. However, if the constraints are easy to satisfy, constraint-based tools usually do not perform as well as stochastic methods. For solving such instances, algorithms should focus on dealing with the objective functions. This paper proposes the integration of stratification techniques in constraint-based algorithms for MOCO. Moreover, it also shows how to diversify the stratification among the several objective criteria in order to better approximate the Pareto front of MOCO problems. An extensive experimental evaluation on publicly available MOCO instances shows that the new algorithm is competitive with stochastic methods and it is much more effective than existing constraint-based methods.
Keywords:
Constraints and SAT: Constraint Optimisation
Heuristic Search and Game Playing: Combinatorial Search and Optimisation
Constraints and SAT: SAT: Applications
Constraints and SAT: SAT: Solvers and Tools