4 Presentations

• 
  10:30 AM - 10:55 AM

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

  • Philippe Olivier, presenter,
  • Andrea Lodi, Polytechnique Montreal
  • 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.

• 
  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.

• 
  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.

• 
  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.