Journée industrielle des GDR ROD et RADIA

Rencontres entre académiques et industriels sur la programmation mathématique : solveurs, applications et retours d’expérience

Les présentations des orateurs sont disponibles dans le programme ci-dessous.

Nous sommes ravis de vous convier à une rencontre entre académiques et industriels qui se tiendra le 14 décembre 2023 à l'INSA Lyon. Cet événement est organisé conjointement par le GDR Recherche Opérationnelle et Décision (ROD) et le GDR Raisonnement, Apprentissage, et Décision en Intelligence Artificielle (RADIA).

Date : 14 décembre 2023
Heure : 10h00 - 16h00
Lieu : INSA Lyon (arrêt Gaston Berger La Doua,  ligne directe depuis la gare de la Part Dieu)

Inscription
La participation à cet événement est gratuite, mais l'inscription préalable est obligatoire afin de prévoir les pauses et le déjeuner (offerts par les GDR ROD et RADIA). Veuillez vous inscrire avant le 1^er décembre en répondant au sondage suivant : https://evento.renater.fr/survey/journee-industrielle-gdr-rod-radia-14-decembre-2023-a-l-insa-lyon-dihxnrx9

Objectif
Cette journée vise à fournir un aperçu des techniques de programmation mathématique telles que la programmation par contraintes (CP), la satisfiabilité booléenne (SAT), et la programmation linéaire en nombres entiers (ILP), par exemple. Nous mettrons l'accent sur leur application pratique dans un contexte industriel ainsi que sur les solveurs existants. Cette journée sera l'occasion d'explorer les cas réels où ces approches ont été utilisées avec succès. Notre public cible est constitué d'industriels et de professionnels intéressés par la modélisation et la résolution de problèmes combinatoires complexes. Que vous soyez chercheur, ingénieur, ou gestionnaire de projet, cette journée offre une opportunité unique d'apprendre et d'échanger sur des approches avancées en optimisation et résolution de problèmes.

Programme
La journée sera rythmée par des exposés présentant des outils, des méthodologies, et des retours d'expérience d'industriels qui ont intégré la programmation mathématique dans leurs activités. Les sujets abordés incluront la modélisation de problèmes complexes, les techniques de résolution, et les avantages observés en termes d'efficacité opérationnelle et de prise de décision. Le programme est en cours d’élaboration, mais nous pouvons d’ors et déjà annoncer les présentations suivantes.

10h : accueil.

10h15-11h00 : Lucas Groleaz (Infologic). Programmation Mathématique dans les ERP : deux cas d'utilisation au sein de l'ERP Copilote

Planches : groleaz.pdf

Résumé. Dans cet exposé nous allons aborder deux cas d'utilisation de la programmation mathématique au sein de l'ERP Copilote, qui est un progiciel spécialisé dans le domaine de l’agroalimentaire. La première utilisation concerne les problèmes d'ordonnancement. Nous parlerons notamment des différentes contraintes auxquelles sont confrontés les utilisateurs de Copilote lorsqu'ils doivent résoudre des problématiques d'ordonnancement. Nous aborderons également le sujet des solveurs utilisés avec notamment une comparaison de CPLEX (programmation linéaire), CP-Optimizer et Ortools (Programmation par Contrainte / SAT). La seconde utilisation concerne un problème de rangement optimal (un dérivé de Bin Packing) pour lequel OrTools est utilisé en production. Nous aborderons notamment la problématique de paramétrage de l'ERP (et donc des modèles mathématiques utilisés) pour adapter le programme au besoin de chaque utilisateur. Nous conclurons en parlant des raisons qui nous poussent à choisir tantôt la programmation mathématique tantôt d'autres techniques de résolution (heuristiques, métaheuristiques, ...).

11h00-11h45 : Christophe Lecoutre (CRIL, Université d’Artois). PyCSP3, une bibliothèque moderne pour la modélisation et résolution de problèmes combinatoires sous contraintes

Planches : lecoutre.pdf

Résumé. Lors de cet exposé, nous commencerons par présenter les fonctionnalités majeures de la librairie PyCSP3 (pycsp.org), qui permet de modéliser tout type de problèmes combinatoires (à variables entières) sous contraintes. Nous mettrons en avant la transparence des modèles, et les facilités de contrôle offertes par l'interface (avec, par exemple, l'emploi de Jupyter notebooks). Nous discuterons ensuite des stratégies de résolution (et leur progrès) intégrées dans les solveurs de contraintes.

11h45-12h30 : Alain Nguyen (Renault). La PL/PLNE au cœur des applications d’optimisation dans la chaine logistique de RENAULT

Planches : nguyen.pdf

Résumé. La PL/PLNE a été utilisée intensivement dans les applications de planification de production à court et moyen terme chez RENAULT, et ce depuis 3 décennies. En amont de la planification, nous avons utilisé la PL/PLNE pour contrôler/affiner les prévisions commerciales. Plus récemment, nous avons eu recours à la PL/PLNE dans des outils d’aide à la décision (what-if scenario) pour les managers logistiques. Enfin, l’usage de la PL/PLNE s’est étendue à la conception du réseau de transport des fournisseurs vers les usines. Selon la volumétrie des données, nous avons soit résolu le problème d’optimisation « frontalement » avec la PL/PLNE, soit décomposé le problème initial en sous-problèmes solubles pour la PL/PLNE. Toutes ces problématiques d’optimisation ont été multi-objectifs (traités en lexicographique). Pour être complet, nous évoquerons enfin les problématiques d’optimisation dans la chaine logistique que nous n’avons pas pu traiter par la PL/PLNE.

12h30-13h45 : pause déjeuner

13h45-14h30 : Philippe Laborie (LocalSolver). Solveurs mathématiques pour les problèmes d'ordonnancement (une vie existe au-delà de la PLNE)

Planches : laborie.pdf

Résumé. Ces dernières années ont vu le développement de solveurs mathématiques utilisant des concepts de modélisation plus riches que la PLNE, notamment pour les problèmes d'ordonnancement. Ces solveurs sont aujourd'hui largement utilisés dans l'industrie, ont des performances souvent comparables aux meilleurs algorithmes dédiés, permettent des modélisations compactes, passent à l'échelle (taille du problème, complexité) et sont en constante amélioration. Nous présenterons leurs principales caractéristiques en les illustrant, entre autres, avec LocalSolver.

14h30-15h15 : Laurent Perron (Google). CP-SAT in OR-Tools

Planches : perron.pdf

Abstract. The CP-SAT-LP solver is developed by the Operations Research team at Google and is part of the OR-Tools open-source optimization suite. It is an implementation of a purely integral Constraint Programming solver on top of a SAT solver using Lazy Clause Generation. It draws its inspiration from the chuffed solver, and from the CP 2013 plenary by Peter Stuckey on Lazy Clause Generation. The CP-SAT-LP solver improves upon the chuffed solver in two main directions. First, it uses a simplex alongside the SAT engine. Second, it implements and relies upon a portfolio of diverse workers for its search part. The use of the simplex brings the obvious advantages of a linear relaxation on the linear part of the full model. It also started the integration of MIP technology into CP-SAT-LP. This is a huge endeavour, as MIP solvers are mature and complex. It includes presolve -- which was already a part of CP-SAT --, dual reductions, specific branching rules, cuts, reduced cost fixing, and more advanced techniques. It also allows the tight integration of the research from the Scheduling on MIP community along with the most advanced scheduling algorithms. This has enabled breakthroughs in solving and proving hard scheduling instances of the Job-Shop problems and Resource Constraint Project Scheduling Problems. Using a portfolio of different workers makes it easier to try new ideas and to incorporate orthogonal techniques with little complication, except controlling the explosion of potential workers. These workers can be categorized along multiple criteria like finding primal solutions -- either using complete solvers, Local Search or Large Neighborhood Search --, improving dual bounds, trying to reduce the problem with the help of continuous probing. This diversity of behaviors has increased the robustness of the solver, while the continuous sharing of information between workers has produced massive speedups when running multiple workers in parallel. All in all, CP-SAT-LP is a state-of-the-art solver, with unsurpassed performance in the Constraint Programming community, breakthrough results on Scheduling benchmarks (with the closure of many open problems), and competitive results with the best MIP solvers (on purely integral problems).

15h15-16h00 : Jean-Marie Lagniez (CRIL, Université d’Artois). Modélisation et résolution de problèmes avec SAT

Planches : lagniez.pdf

Résumé. Les solveurs SAT jouent un rôle clé dans la résolution de problèmes combinatoires divers. Cette présentation explore deux contextes distincts où l'efficacité des solveurs SAT peut être considérablement améliorée en adaptant leur approche à la nature spécifique des problèmes. Nous débuterons par une introduction succincte du problème SAT et des solveurs CDCL. Dans le cadre du calcul de l'ensemble minimal insatisfaisable (MUS), nous mettons en évidence l'impact positif sur les performances en intervenant sur le nettoyage de la base de clauses, la gestion des hypothèses, et d'autres paramètres classiques. Ces ajustements se révèlent particulièrement fructueux pour optimiser une tâche intensive de résolution SAT incrémentale basée sur des hypothèses. Enfin, nous aborderons la résolution du problème de formation d'équipe (TF) en utilisant la technologie SAT. Nous démontrons qu'afin de résoudre ce problème, impliquant une couverture d'ensemble avec une contrainte de grande cardinalité, il est plus judicieux d'opter pour un solveur MaxSAT plutôt qu'un solveur SAT conventionnel. Cette analyse souligne de manière probante l'inefficacité des solveurs SAT dans le traitement adéquat des contraintes de grande cardinalité.

Contact
Pour toute question ou demande de renseignements supplémentaires, n'hésitez pas à nous contacter. Nous espérons vous accueillir nombreux à cette journée passionnante dédiée à l'exploration des applications concrètes de la programmation mathématique dans le monde industriel.

Jean-Marie Lagniez, Claude Le Pape-Gardeux, Aziz Moukrim et Christine Solnon