Prediction-based propagation in constraint programming: A focus on the AllDifferent constraint

Details

Supervisors

Verhaeghe, Hélène

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] : ingénieur civil en informatique, à finalité spécialisée

Abstract

enConstraint programming is a very interesting approach when one is looking for a set of correct solutions to a problem that can be modeled as variables with specific domains linked by constraints. However, for many problems, the time required to find these solutions, as well as the size of the search tree, can present a significant challenge. This thesis aims to build a proof of concept by constructing an AllDifferent propagator based on machine learning in order to simulate the behavior of the Domain Consistency propagator. The goal is, through a variable threshold that modifies the model’s behavior, to more or less reduce the search tree and thereby find solutions more quickly that are uniformly distributed within this tree. The approach also applies to constraint optimization problems (COPs), in order to assess whether the constructed model is capable of finding a solution, subject to an optimization function, that is sufficiently close to the best solution obtained using a classical solver.