Journée "RO et Contraintes" - 31 mai 2022
La journée a réuni 26 participants de toute la France et a été l'occasion de rencontres et d'échanges enrichissants.
Le groupe de travail "Recherche Opérationnelle et Contraintes" du GdR RO organise une journée thématique sur le campus Saint-Jean d'Angely à Nice le 31 mai 2022. Plus précisemment, la journée aura lieu dans la salle 2B30 du bâtiment SJA2 (voir plan). L'accueil du bâtiment sera ouvert si vous avez des difficultés à trouver la salle.
Le thème de la journée est la résolution des problèmes d'ordonnancement, de transport et à plus large échelle de tout problème de recherche opérationnelle résolu par la programmation par contraintes ou des méthodes hybrides. L'objectif de cette journée est de créer un lieu d'échange pour les doctorants et les chercheurs impliqués dans sa thématique.
Vous pouvez présenter en anglais ou en francais selon votre préférence. Le format des exposés est l'un des suivants :
- Exposé : 20min de présentation + 10min de questions.
- Pitch : 5min de présentation + 10min de questions.
Horaire | Activité |
---|---|
09h00 - 10h00 | Accueil / Café |
10h00 - 11h00 | Sequence Variables for Routing Problems - Pierre Schaus |
11h00 - 11h30 | Arc-consistency and linear programming duality - Hadrien Cambazard |
11h30 - 12h00 | Logic-based Benders decomposition for the preemptive Flexible Job-Shop Scheduling Problem - Carla Juvin |
12h00 - 12h30 | Tirage de solutions par ajout de contraintes tables aléatoires - Mathieu Vavrille |
12h30 - 14h30 | Déjeuner |
14h30 - 14h45 | Scheduling with Component Health Index : towards a CP approach - Ernest Foussard |
14h45 - 15h15 | Intérêts et utilisations des MDD dans la résolution de problèmes - Victor Jung |
15h15 - 15h45 | La contrainte d'Allen - Jean-Charles Régin |
15h45 - 16h15 | Discrete Optimization with Decision Diagrams - Xavier Gillard |
16h15 - 16h30 | Des MDD pour résoudre des équations définies sur des Systèmes Dynamiques Discrets - Sara Riva |
16h30 - 17h30 | Goûter / Discussion |
Vous trouverez ci-dessous le programme détaillé de la journée avec les titres et résumés des exposés.
Sequence Variables for Routing Problems - Pierre Schaus
Constraint Programming (CP) is one of the most flexible approaches for modeling and solving vehicle routing problems (VRP). In this talk, I will introduce the sequence variable domain, that is inspired by the insertion graph and the subset bound domain for set variables. This domain representation, which targets VRP applications, allows for an efficient insertion-based search on a partial tour and the implementation of simple, yet efficient filtering algorithms for constraints that enforce time-windows on the visits and capacities on the vehicles. I will show some experimental results that hopefully will convince you about the efficiency and flexibility of this CP domain for solving some hard VRP problems, including the Dial A Ride, the Patient Transportation, and the asymmetric TSP with time windows.
Arc-consistency and linear programming duality - Hadrien Cambazard
In Constraint Programming (CP), achieving arc-consistency (AC) of a global constraint with costs consists in removing from the domains of the variables all the values that don't belong to any solution whose cost is below a fixed bound (assuming minimization). We analyse how linear duality and reduced costs can be used to find all such inconsistent values. In particular, when the constraint with costs has an ideal Linear Programming (LP) formulation, we show that n dual solutions are always enough to achieve AC (where n is the number of variables of the constraint). We will discuss the design of a generic primal-dual algorithm for filtering.
Logic-based Benders decomposition for the preemptive Flexible Job-Shop Scheduling Problem - Carla Juvin
We focus on exact methods to solve the preemptive Flexible Job-Shop Scheduling Problem with makespan minimisation objective function. Mathematical and constraint programming models enable the resolution of this problem for small instances. However, as an NP-hard problem, the cost of solving grows rapidly when considering larger instances. In this regard, we propose a logic-based Benders decomposition that relies on an efficient branch-and-bound procedure to solve the subproblem representing a pure (non-flexible) preemptive job-shop scheduling problem. Computational experiments are carried out and show the very good performance of our proposals.
Tirage de solutions par ajout de contraintes tables aléatoires - Mathieu Vavrille
Les solveurs de contraintes actuels mettent à disposition des utilisateurs des algorithmes efficaces pour traiter les problèmes de satisfaction et d'optimisation combinatoires. Ceux-ci sont inadaptées à de nouveaux usages, comme celui du tirage aléatoire de solutions. Nous proposons ici un algorithme pour tirer des solutions aléatoirement, se basant sur l'ajout de contraintes tables générées aléatoirement, sans modifier le modèle du problème. Nous avons implémenté cette méthode de résolution en utilisant un solveur de contraintes existant. Nos expériences montrent que cet algorithme est une amélioration par rapport à une stratégie de branchement aléatoire en terme de qualité de l'aléatoire du tirage.
TBD - Victor Jung
La contrainte d'Allen - Jean-Charles Régin
La contrainte "Allen" est une contrainte globale reliant les index d’événements aux positions temporelles. En présence de séquences temporelles, une approche typique des contraintes consiste à modéliser chaque événement temporel de la séquence avec une variable et d’énoncer des contraintes sur ces variables indexées. Cependant, cette approche entrave l’énoncé de contraintes impliquant des événements basés sur la position temporelle puisque la position dépend des événements précédents plutôt que de l’indice.
La contrainte Allen maintient deux variables ensemblistes : l’ensemble d’événements se produisant à une position définie par une relation de Allen, et l’ensemble de leurs index. Ces variables permettent de renforcer les propriétés de synchronisation structurelle et temporelle qui ne peuvent être énoncées sur des variables indexées. La contrainte Allen utilise intelligemment un MDD.
Cette contrainte est utilisée pour énoncer et résoudre deux tâches musicales complexes : la synchronisation de pistes audio et la génération de partitions musicales qui ne peuvent être résolus que pour des très petites tailles avec un modèle d’ordonnancement classique. Ce travail a été fait en collaboration avec les chercheurs de Sony CSL Paris
Discrete Optimization with Decision Diagrams - Xavier Gillard
Discrete Optimization with Decision Diagrams is a novel paradigm that combines the same dynamic programming approach which serves as a basis for countless classic algorithms (Dijkstra, Bellman-Ford or Viterbi to name a few) with decision diagrams. The rationale behind that combination is that in many cases, finding a true optimal solution for a given dynamic program is intractable because of the state space explosion that arises from the combinatorial nature of the problems being solved. To deal with such cases, a method was devised using decisions diagrams which guarantees to only use a polynomial amount of time and memory to derive (upper and lower) bounds on the problem at hand. In this talk, I will present the intuitions governing that novel paradigm. Using the traveling salesman problem with time windows as an example, I will show how one can use that paradigm to efficiently solve hard combinatorial problems with a generic framework.