4 Presentations

• 
  03:30 PM - 03:55 PM

  A O(n log^2 n) checker and O(n^2 log n) filtering algorithm for the energetic reasoning

  • Yanick Ouellet, presenter, Université Laval
  • Claude-Guy Quimper, Université Laval

  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.

• 
  03:55 PM - 04:20 PM

  Solving systems of linear equalities in modular arithmetic with applications to model counting in CP

  • Mahshid Mohammadalitajrishi, presenter, polytechnique montreal
  • Gilles Pesant, Polytechnique Montréal

  Model counting and sampling are two important problems in artificial intelligence. A previously proposed approach for SAT models, inspired by universal hashing, adds randomly-generated XOR constraints to partition the solution space until each cell becomes tractable. We generalize this approach to CP models by considering randomly-generated 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.

• 
  04:20 PM - 04:45 PM

  Accelerating counting-based search

  • Samuel Gagnon, presenter, École Polytechnique Montréal
  • Gilles Pesant, Polytechnique Montréal

  Counting-based search, a branching heuristic used in constraint programming, relies on computing the proportion of solutions to a constraint in which a given variable-value assignment appears in order to build an integrated variable- and value-selection 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 counting-based search, with supporting empirical evidence that solutions can thus be obtained orders of magnitude faster.

• 
  04:45 PM - 05:10 PM

  Getting more out of the exposed structure in constraint programming models of combinatorial problems

  • Gilles Pesant, presenter, Polytechnique Montréal

  To solve combinatorial problems, Constraint Programming builds high-level 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 structure-revealing 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.