2018 Optimization Days

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

Schedule Authors My Schedule
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

TA3 Constraint programming I

May 8, 2018 10:30 AM – 12:10 PM

Location: EY (69)

Chaired by Gilles Pesant

4 Presentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    10:30 AM - 10:55 AM

    A comparison of optimization methods for multi-objective constrained bin packing problems

    • Philippe Olivier, presenter,
    • Andrea Lodi, Polytechnique Montréal
    • Gilles Pesant, Polytechnique Montréal

    In practice, bin packing problems often feature various considerations such as pairwise conflicts or profits between items, or aiming for balanced loads amongst the bins. We present a constraint programming model and two integer programming models of such problems and compare them empirically to a metaheuristic approach.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    10:55 AM - 11:20 AM

    The WeightedCircuitsLmax constraint

    • Kim Rioux-Paradis, presenter, Université Laval
    • Claude-Guy Quimper, Université Laval

    The travelling salesman problem is a well-known problem that can be generalized to the m-travelling salesmen where the objective is to minimize the longest circuit travelled. We generalize the Circuit and WeightedCircuit constraints and present a new constraint that encodes m cycles all starting from the same city and whose lengths are bounded by a variable Lmax.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    11:20 AM - 11:45 AM

    Automatic melody generation using constraint programming

    • Alexandre Briand, presenter, École Polytechnique de Montréal
    • Gilles Pesant, Polytechnique Montréal

    We are developing a hierarchical constraint system to generate a melody given an existing melody and a chord sequence. Using suffix trees, we extract structural characteristics from the given example. The user will then be able to decide which of the extracted patterns he wants to replicate in the output, how close to the original he wants them to sound and also add his own constraints.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    11:45 AM - 12:10 PM

    Modelling disjunctive constraints using time interval variables

    • Rachid Cherkaoui, presenter, Polytechnique Montréal

    We show that computing domain consistency for the disjunctive constraint is Fixed Parameter Tractable. This can be achieved by a dynamic programming algorithm that computes a set of time intervals for each task. These intervals can serve as variables for branching and filtering. We expect that hybridization with conventional branching techniques for disjunctive scheduling can improve the search.