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

10h30  10h55
A comparison of optimization methods for multiobjective constrained bin packing problems
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.

10h55  11h20
The WeightedCircuitsLmax constraint
The travelling salesman problem is a wellknown problem that can be generalized to the mtravelling 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.

11h20  11h45
Automatic melody generation using constraint programming
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.

11h45  12h10
Modelling disjunctive constraints using time interval variables
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.