New Constraint Programming Approaches for the Computation of Leximin-Optimal Solutions in Constraint Networks

The authors study the problem of computing a leximin optimal solution of a constraint network. This problem is highly motivated by fairness and efficiency requirements in many real-world applications implying human agents. They compare several generic algorithms which solve this problem in a constraint programming framework. The first one is entirely original, and the other ones are partially based on existing works adapted to fit with this problem. Many advances have been done in recent years in modeling and solving combinatorial problems with Constraint Programming (CP). These advances concern, among others, the ability of this framework to deal with human reasoning schemes, such as, for example, the expression of preferences with soft constraints.