Evolution of search trees and order heuristics for constraint problems – EVARISTE

The EVARISTE project proposes a new approach to optimize solution exploration strategies used by exact resolution methods dedicated to solve combinatorial constraint satisfaction problems. These methods generally rely on building a decision tree that gradually constructs a solution, satisfying the various constraints of the problem and potentially optimizing an objective. By using concepts and methodologies from evolutionary algorithms and fitness landscapes analysis, the goal is to develop more effective order heuristics for the decision variables of the problem and the selection of their values for classical tree-based exploration of the solution space. This involves shifting the focus from solving combinatorial problems in the initial search space to exploring the space of heuristics with appropriate metrics, leading to the discovery of new strategies for solvers.
The fundamental challenge of determining an optimal sequence will be intricately connected to a challenging optimization issue known as the "distance geometry problem," which will play a central role in our approach.
Ultimately, this work seeks to provide an alternative and explanatory approach to constraint solvers, which are frequently treated as black-box systems, using analytical tools and identified characteristics.