Journée "RO et Contraintes" - 31 mai 2022

Organisateur:

Intitulé: 
Journée "RO et Contraintes"
Date: 
Mardi, 31 Mai, 2022

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.

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 :

  1. Exposé : 20min de présentation + 10min de questions.
  2. Pitch : 5min de présentation + 10min de questions.
Programme de la journée
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 La contrainte d'Allen - Jean-Charles Régin
15h15 - 15h45 Intérêts et utilisations des MDD dans la résolution de problèmes - Victor Jung
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 dual variables). 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.