2018 Optimization Days

HEC Montréal, Québec, Canada, May 7 — 9, 2018

Schedule Authors My Schedule
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

TB3 Constraint programming II

May 8, 2018 03:30 PM – 05:10 PM

Location: EY (69)

Chaired by Gilles Pesant

4 Presentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    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.