Autonomous Constraint Solvers
- PhD Student:
- Hugues Wattez
- Co-Supervisor :
- Anastasia Paparrizou
- Funding : Artois, Région HdF
- PhD defended on :
- Dec 9, 2021
Constraint programming is declarative: the user models the problem (in the form of constraints) without worrying about the solving part. The solving is delegated to a generic program called a constraint solver.
Constraint solvers use mechanisms from artificial intelligence to guide its choices (heuristics), and to efficiently reduce the search space (inference). Recent constraint solvers are equipped with several heuristics. Choosing the best heuristic to solve a given problem instance is currently delegated to the user.
The goal of this thesis is to make constraint solvers more autonomous. We want to remove any cognitive burden from the user regarding the solving process. While searching for solutions, the solver often restarts the search to avoid expensive dead-ends. We propose to automatically select the most promising heuristic after each restart.
In response to this sequential choice problem, we take inspiration from policies addressing the multi-armed bandit problem. Such policies are derived from reinforcement learning and allow to explore a set of actions while exploiting the most profitable one as often as possible.
After having defined how to incorporate this machine learning tool in a solver, we propose several applications to make modern constraint solvers more autonomous. First, we apply the policies proposed in the multi-armed-bandits literature to learn the best heuristic among a set of heuristics provided by the solver. Based on this first application, we propose a new policy that is more consistent with the structure of current solvers. Still using bandit policies, we propose to adapt the amount of randomization needed to perturb a given heuristic and make it more efficient. Finally, we extend these results to constraint optimization solvers.
- Frédéric Koriche, Université d’Artois, Lens
- Christophe Lecoutre, Université d’Artois, Lens
- Anastasia Paparrizou, CNRS, Lens
- Marie-José Huguet, INSA, Toulouse
- Thomas Schiex, INRAE, MIA, Toulouse
- Cyril Terrioux, Université d’Aix-Marseille
- Rémy Bardenet, Université de Lille
- Sébastien Tabary, Université d’Artois, Lens
- Sonia Vanier, LIX, Université Paris1