Ultra-weak solutions and consistency enforcement in minimax weighted constraint satisfaction

International audienceThe task at hand is that of a soft constraint problem with adversarial conditions. By amalgamating the weighted and quantified constraint satisfaction frameworks, a Minimax Weighted Constraint Satisfaction Problem (formerly Quantified Weighted Constraint Satisfaction Problem) consists of a set of finite domain variables, a set of soft constraints, and a min or max quantifier associated with each of these variables. We formally define the framework, suggest three solution concepts, and propose a complete solver based on alpha-beta pruning techniques. We discuss in depth our novel definitions and implementations of node, arc and full directional arc consistency notions to help reduce search space on top of the basic tree search with alpha-beta pruning for solving ultra-weak solutions. In particular, these consistencies approximate the lower and upper bounds of the cost of a problem by exploiting the semantics of the quantifiers and reusing techniques from both Weighted and Quantified Constraint Satisfaction Problems. Lower bound computation employs standard estimation of costs in the sub-problems used in alpha-beta search. In estimating upper bounds, we propose two approaches based on the Duality Principle: duality of quantifiers and duality of constraints. The first duality amounts to changing quantifiers from min to max, while the second duality re-uses the lower bound approximation functions on dual constraints to generate upper bounds. Experiments on three benchmarks comparing basic alpha-beta pruning and the six consistencies from the two dualities are performed to confirm the feasibility and efficiency of our proposal