Séminaire DKM : Randomization of solutions in constraint programming

Constraint programming provides generic techniques to efficiently solve combinatorial problems. In this talk, I will present an ongoing work on constraint sampling. The question is: is it possible to sample combinatorial problems in a generic way, using a constraint solver, and without making the computation time explode? I will present an algorithm, inspired from Meel’s method on SAT, to add randomly chosen hashing constraints to the problem, in order to split the search space into small cells of solutions. By sampling the solutions in a cell, it randomly generates solutions without revamping the model of the problem. We ensure the randomness by introducing a new family of hashing constraints: randomly generated tables. We implemented this solving method using the constraint solver Choco-solver. The quality of the randomness and the running time of our approach are experimentally compared to a random branching strategy. We show that our approach improves the randomness while being in the same order of magnitude in terms of running time.En espérant vous voir nombreux !