Accueil des participants

Optimisation dans les modèles graphiques et applications

Thomas Schiex

INRA Toulouse

En IA, les modèles graphiques sont habituellement compris comme étant des modèles stochastiques dont la structure d'indépendance est capturée par un graphe. Il s'agit par exemple des réseaux bayésiens ou des champs aléatoires de Markov (MRF). Dans ces modèles, une probabilité de distribution jointe sur un ensemble de variables aléatoires discrètes est représentée de façon concise par la combinaison de fonctions locales.

Cette même idée a été utilisée dans des versions déterministes telles que les réseaux de contraintes. Je m'intéresserai ici à leur version pondérée (ou réseaux de fonctions de coûts, CFN). Une fonction de coût globale est représentée par la combinaison de fonctions locales (clauses pondérées en SAT, fonctions de coûts pour les CFN).

Cette concision a un coût: l'optimisation devient NP-difficile. De ce fait, des méthodes d'inférence efficaces ont été définies, telles que le "message passing" (MRF), les cohérences locales (CFN) ou la résolution et la propagation unitaire (SAT).

Dans cette présentation, j'essaierai de donner une présentation unifiée de ces approches, dans le contexte de l'optimisation, en montrant en particulier qu'elles s'interprètent comme des résolutions approchées d'un programme linéaire spécifique, redécouvert à de multiples reprises.

Pour finir, je poursuivrais cette exploration des frontières entre PC/IA/RO en m'appuyant sur le problème de design algorithmique de protéines, modélisé et traité via des formalismes variés: PLNE (Cplex), programmation quadratique (Cplex et BiqMac), MaxSAT, CFN et outil dédié élaboré par les biophysiciens.

Pause déjeuner

The NValue global constraint

Hadrien Cambazard

G-SCOP - Grenoble

Global constraints are a core component of Constraint Programming (CP) solvers and once made the success of CP. We focus in this talk on the NValue global constraint, which restricts the number of distinct values taken by a set of variables. It is a well known NP-Hard global constraint that occur in many industrial applications where the number of some resources have to be minimized. We will illustrate some applications of this constraint and explain the existing filtering algorithms. In particular, we will present a recent filtering algorithm relying on Lagrangian relaxation.

Heuristiques de recherche en programmation par contraintes

Jean-Guillaume FAGES

COSLING

La programmation par contraintes est une technique de résolution de problèmes reposant principalement sur les concepts de filtrage et d'exploration. Cet exposé propose une introduction aux principales techniques d'exploration d'un espace de recherche, dans le but de susciter de nouvelles contributions mêlant RO et IA. Nous présenterons des heuristiques génériques et métiers ainsi que des hybridations avec des recherches locales. Nous illustrerons ces concepts au travers d'exemples basés sur le solveur Choco, qui est avant tout un framework d'intégration d'algorithmes pour les communautés RO et IA.

Pause café

Solving Industrial Scheduling Problems with Constraint Programming

Philippe Laborie

IBM

Scheduling problems represent an important class of application for Constraint Programming (CP) in the industry. For more than 20 years, our team at ILOG (now IBM) has been developing CP technology and applying it to solve our customers' scheduling problems. In the first part of the talk, we will present some extensions of CP (interval variables, functions, sequences) that capture the temporal dimension of scheduling and make it possible/easier to design efficient models for complex problems. But a powerful modeling language is not sufficient: in an industrial context, one must also simplify the complete process of model design (connection to data, data processing and consistency checking, model debugging, etc.) and problem resolution (robust automatic search algorithm, warm start, model chaining, etc.), this will be the topic of the second part of the talk. The presentation will be illustrated with examples using IBM ILOG CP Optimizer.

Optimal routing in deterministic delay-tolerant networks

Ronan Bocquillon

Heudiasyc

Transparents de la présentation

Delay-Tolerant Networking is a promising approach to address technical issues in networks that are subject to frequent partitioning (termed intermittently-connected networks). In particular, the Delay-Tolerant Network (DTN) architecure was designed to ensure interoperability, performances, and security in heterogeneous networks where end-to-end paths may never exist. In this talk, we will focus on the problem of routing in DTNs. The common approach is to use a store-carry-forward mechanism, i.e. data are sent from one node to another, depending on the communication opportunities that arise, and stored throughout the network in hope that messages will reach their destination. We will assume reliable predictions can be made about node mobility, and will thus study the problem of making use of this knowledge when data need to be routed from one subset of nodes to another within a given time horizon. Applications include satellite and interplanetary networks (where the trajectory of nodes depends on straightforward physics), fleets of drones, and public transportation systems. First the problem will be formalized. Next we will propose a constraint-programming-based approach to solve it.