| Event Details |
|---|
|
Thursday, November 6, 2014 Talk:
4:00 p.m., Avery 115
Reception:
3:30 p.m., Avery 348
|
Nicolas Bonifas
Ph. D. Student, École PolytechniqueAbstract
The most fundamental global constraint used in constraint-based scheduling is the cumulative constraint, so its efficient propagation is of critical practical importance.
After setting the context, we will introduce a reformulation of the cumulative constraint which tightens the resource consumptions, enabling much stronger propagation, without losing any feasible solution. We give guarantees on the quality of this reformulation. This reformulation relies on a linear program whose size depends on the capacity of the resource but not on the number of tasks, which enables to precompute the reformulations. It provides a significant improvement for all existing propagations of the cumulative constraint, such as edge-finding techniques.
Time permitting, we will also sketch a recent improvement to the complexity of one of the strongest propagations available for the cumulative constraint, namely the energy reasoning of Erschler and Lopez. In spite of its strength it is seldom used because of its O(n^3) complexity. We introduce an algorithm to compute this propagation in time O(n^2 log(n)) which significantly improves on the algorithm which has been known for 25 years. This new approach relies on novel properties of the cumulative constraint and on a geometric study.
After setting the context, we will introduce a reformulation of the cumulative constraint which tightens the resource consumptions, enabling much stronger propagation, without losing any feasible solution. We give guarantees on the quality of this reformulation. This reformulation relies on a linear program whose size depends on the capacity of the resource but not on the number of tasks, which enables to precompute the reformulations. It provides a significant improvement for all existing propagations of the cumulative constraint, such as edge-finding techniques.
Time permitting, we will also sketch a recent improvement to the complexity of one of the strongest propagations available for the cumulative constraint, namely the energy reasoning of Erschler and Lopez. In spite of its strength it is seldom used because of its O(n^3) complexity. We introduce an algorithm to compute this propagation in time O(n^2 log(n)) which significantly improves on the algorithm which has been known for 25 years. This new approach relies on novel properties of the cumulative constraint and on a geometric study.
Speaker Bio
Nicolas Bonifas is an alumni of the ÉNS Lyon, France and currently a Ph.D. student at the École Polytechnique, Paris, France under the supervision of Prof. Philippe Baptiste and at IBM Ilog where he works in the CP Optimizer group with Dr. Philippe Laborie, Dr. Jérôme Rogerie, and Dr. Petr Vilím. His background is in mathematics and computer science with a deep interest in optimization. He especially likes using strong theory to solve practical problems. He has also been working on theoretical topics in optimization, notably on bounding the diameter of polytopes and on combinatorial and geometrical properties of Euclidean lattices.