Homepage
Previous JFRO
Organizing committee
Contact
34th Ile-de-France Operation Research Day
Programmation par contraintes pour l'intelligence artificielle et la recherche opérationnelle
Date
This day took place
Wednesday, the 23 September 2015
Place
Conservatoire National des Arts et Métiers (Amphi Friedmann, accès 33, 2ème étage, 33.2.20) 2, rue Conté, 75003 Paris

Program of the day


09h30-10h00
Accueil des participants

10h00-12h00
Optimisation dans les modèles graphiques et applications
Thomas Schiex (INRA Toulouse)
Abstract : 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.

12h00-14h00
Pause déjeuner

14h00-14h40
The NValue global constraint
Abstract : 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.

14h40-15h20
Heuristiques de recherche en programmation par contraintes
Abstract : 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.

15h20-15h40
Pause café

15h40-16h20
Solving Industrial Scheduling Problems with Constraint Programming
Abstract : 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.

16h20-17h00
Optimal routing in deterministic delay-tolerant networks
Ronan Bocquillon (Heudiasyc)
Abstract : 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.

Choose language : Français English