Journées de l'optimisation 2018
HEC Montréal, Québec, Canada, 7 — 9 mai 2018
TB3 Constraint programming II
8 mai 2018 15h30 – 17h10
Salle: EY (69)
Présidée par Gilles Pesant
4 présentations

15h30  15h55
A O(n log^2 n) checker and O(n^2 log n) filtering algorithm for the energetic reasoning
Energetic reasoning is a strong filtering technique for the Cumulative constraint. However, the best algorithms process O(n^2) time intervals to perform the satisfiability check which makes it too costly to use in practice. We present how to apply the energetic reasoning by processing only O(n log n) intervals and propose improved checker and filtering algorithms.

15h55  16h20
Solving systems of linear equalities in modular arithmetic with applications to model counting in CP
Model counting and sampling are two important problems in artificial intelligence. A previously proposed approach for SAT models, inspired by universal hashing, adds randomlygenerated XOR constraints to partition the solution space until each cell becomes tractable. We generalize this approach to CP models by considering randomlygenerated linear constraints in modular arithmetic and investigate the opportunities to perform domain filtering and solution counting with such constraints using dynamic programming and Gaussian elimination.

16h20  16h45
Accelerating countingbased search
Countingbased search, a branching heuristic used in constraint programming, relies on computing the proportion of solutions to a constraint in which a given variablevalue assignment appears in order to build an integrated variable and valueselection heuristic to solve constraint satisfaction problems. The information it collects has led to very effective search guidance in many contexts. However, depending on the constraint, computing such information can carry a high computational cost. This paper presents several contributions to accelerate countingbased search, with supporting empirical evidence that solutions can thus be obtained orders of magnitude faster.

16h45  17h10
Getting more out of the exposed structure in constraint programming models of combinatorial problems
To solve combinatorial problems, Constraint Programming builds highlevel models that expose much of the structure of the problem. The distinctive driving force of Constraint Programming has been this direct access to problem structure. This has been key to the design of powerful inference algorithms but we could do much more. Considering the set of solutions to each constraint as a multivariate discrete distribution opens the door to more structurerevealing computations that may significantly change this solving paradigm. As a result we could improve our ability to solve combinatorial problems and our understanding of the structure of practical problems.