Seminars CP @ I3S
Constraint Programming Seminars at the laboratory I3S

<2014-06-19 jeu. 14:00> Berthe Y. CHOUERY est actuellement professeure à l’université du Nebraska-Lincoln.

The tractability of a Constraint Satisfaction Problem (CSP) is guaranteed by a direct relationship between its consistency level and a structural parameter of its constraint network such as the treewidth. This result is not widely exploited in practice because enforcing higher-level consistencies can be costly and can change the structure of the constraint network and increase its width. Recently, we have proposed new algorithms for m-wise consistency (which we denote R(∗,m)C) that do not modify the structure of the graph and, thus, do not affect its width. In my talk, I’ll discuss two main strategies, based on a tree decomposition of the CSP, for improving the performance of enforcing R(∗,m)C and getting closer to the above tractability condition. Those strategies are: a) localizing the application of the consistency algorithm to the clusters of the tree decomposition, and b) bolstering constraint propagation between clusters by adding redundant constraints at their separators, for which we propose three new schemes. We characterize the resulting consistency properties by comparing them, theoretically and empirically, to the original R(∗,m)C and the popular GAC and maxRPWC, and establish the benefits of our approach for solving difficult problems.

<2014-05-14 mer. 10:30> Rita Macedo est actuellement ingénieure de recherche à l’université de Valenciennes et candidate au poste MCF0864.

In this presentation, I will propose a new general solution framework to solve exactly Mixed Integer Programming (MIP) problems that can be formulated as network flow models. The number of nodes of the underlying graphs of these models is typically large and depends on the data values of the addressed problem. To efficiently solve such hard MIP problems, we use the idea of reducing the number of nodes and arcs in the graph, and thus produce an approximate instance (over-constrained or relaxed). The general concept consists of projecting the initial model onto a smaller one, and applying an iterative algorithm based on an aggregation/disaggregation scheme, which refines the model until the optimality is proved. This new algorithmic framework can be applied to a variety of combinatorial problems, such as routing problems, cutting stock, scheduling, etc, and has proved to be quite efficient when compared to other exact approaches in the literature.

<2014-03-14 ven. 15:00> Radoslaw CYMER est actuellement développeur chez Oracle.

One of the most important and most studied areas in constraint programming is global constraints. Global constraints are classes of constraints defined by a relation between a non-fixed number of variables. The talk will deal with matching theory and its application in constraint programming. Based on the existing results of decomposition theory, a universal method will be presented for solving various global constraints. All constraints should have the property that their solution is representable as a matching problem in a particular graph (bipartite graph, general graph, directed graph, weighted graph or hypergraph). The basic idea is to model the solution to the global constraint as a certain matching. The edges belonging to no matching (forbidden edges) can be removed from the auxiliary graph because the corresponding value does not belong to a solution. The partition of edges can be determined with the help of structure theorems discovered by Dulmage and Mendelsohn, Gallai and Edmonds, and Lovasz. Some of the constraints represent NP-complete problems so only incomplete filtering is possible.

<2013-12-05 jeu. 15:00> Stefano DI ALESIO est actuellement doctorant au laboratoire de recherche Simula.

Software applications in safety-critical domains are typically subject to stringent timing constraints which are dictated by the surrounding physical environments. Such constraints are expressed as performance requirements, specifying properties such as bounded response time or CPU usage, or tasks having to finish their execution before given deadlines. The system’s operational safety depends on the satisfaction of these requirements at run-time, and it is therefore important to analyze and test the performance of real-time systems. In this talk, I present a strategy for analyzing and testing the performance of real-time applications. The strategy consists in finding best and worst case scenarios with respect to performance requirements, that can be respectively used to characterize design guidelines, specifying how to design a system to maximize the chance the performance requirements will be met, and stress test cases, specifying how to test a system to maximize the chance the performance requirements will be broken. Such scenarios are identified by searching the possible ways that a set of real-time tasks can be executed according to the scheduling policy of the operating system on which they are running. This search problem is solved using a constraint optimization model that consists of (1) a set of constants capturing the fixed properties of the system, (2) a set of variables capturing the properties of the system that can be manipulated at design time or during testing, (3) a set of constraints capturing how a given set of tasks with real-time constraints are executed according to a pre-emptive fixed priority scheduling policy, and (4) an objective function that estimates how likely the given tasks are to break a given performance requirement.

<2013-12-04 mer. 15:00>

Éric GOUBAULT est actuellement directeur de recherche au CEA et Professeur à l’école Polytechnique.
Co-autrice : Sylvie Putot

Cet exposé decrira succinctement une amélioration de notre analyseur statique par interprétation abstraite, FLUCTUAT, qui compare entre autres choses les exécutions en nombre réels, d’avec celles en précision finie. Un problème de longue date est de déterminer, pour un ensemble d’exécutions possibles, données généralement par des intervalles de valeurs en entrée du programme, une sur-approximation assez fine de la différence entre exécutions flottantes et réelles, de façon efficace, et ceci même quand les flots d’exécution réels et flottants sont divergents. Cet exposé présente une telle méthode, et en discute brièvement les implications en terme de preuve de robustesse/continuité de code, en précision finie, sujet qui a pris de l’importance récemment en vérification et en contrôle.

<2013-10-24 jeu. 11:00> Carmen GERVET est actuellement professeure à German University in Cairo.

In this presentation, we propose to integrate two complementary fields of Information Science, namely fuzzy regression analysis and constraint-based reasoning. The main goal is to be able to develop decision support systems for optimization problems with measurement uncertainty requiring predictive/forecasting data models. Recently, models derived from fuzzy regression analysis have been defined as a non-statistical approach to represent incomplete and imprecise measurements. They are essentially used in complex systems analysis seeking a correlation between crisp or fuzzy measurements. Also, the constraint programming paradigm has proved successful to tackle decision and optimization problems in planning and resource optimization. Interestingly, it handles some forms of uncertainty, but has not, to our knowledge, been enhanced to deal with fuzzy regression models. Our vision are threefold: 1) to study the theoretical aspect of integrating two complementary paradigms, 2) to design and implement an interval regression constraint system, and 3) to apply it to a case study in the field of Renewable Energies (RE) techno-economics, problem of RE portfolio optimization for short and longer term. The means of integration of the two paradigms raise questions which will be brought up for discussions and possible collaborations.

<2013-10-03 jeu.> Chu Min LI est actuellement professeur à l’Université de Picardie Jules Verne.

Le problème MaxClique consiste à trouver une clique (un sous-graphe complet) de taille maximum dans un graphe. La résolution exacte du problème MaxClique nécessite de calculer une borne supérieure de la taille d’une clique maximum. En 2003, Jean-Charles Régin a montré que les techniques CSP sont très utiles pour résoudre le problème MaxClique, notamment en permettant une borne supérieure de bonne qualité et un filtrage des sommets du graphe qui ne peuvent pas faire partie de la clique maximum. Dans cet exposé, nous présentons dans un premier temps les efforts poursuivis depuis 2003 dans l’amélioration de la borne supérieure de la taille d’une clique maximum en exploitant des techniques CSP comme la propagation des contraintes booléennes. Comme une instance CSP peut être naturellement transformée en une instance MaxClique, un algorithme MaxClique peut aussi être utilisé pour résoudre le problème CSP. Nous présentons dans un deuxième temps la résolution CSP en passant par MaxClique. Les perspectives dans les interactions entre le problème MaxClique et le CSP sont discutées à la fin de l’exposé.

<2013-05-30 jeu.>

<2013-01-21 lun.>

<2012-11-16 ven.> Catherine DUBOIS est actuellement Professeur à l’École Nationale Supérieure d’Informatique pour l’Industrie et l’Entreprise.
Co-auteurs : M. Carlier, C. Dubois , A. Gotlieb

Constraint programs such as those written in modern Constraint Programming languages and platforms aim at solving problems coming from optimization, scheduling, planning, etc. Recently CP programs have been used in business-critical or safety-critical areas as well, e.g., e-Commerce, air-traffic control applications, or software verification. This implies a more skeptical regard on the implementation of constraint solvers, especially when the result is that a constraint problem has no solution, i.e., unsatisfiability. We present a Coq formalisation of a constraint filtering algorithm — AC3 and one of its variant AC2001 — and a simple labeling procedure, focing on arc-consistency. The proof of their soundness and completeness has been completed using Coq. As a result, a formally certified constraint solver written in OCaml has been automatically extracted from the Coq development. The solver, yet not as efficient as specialized existing (unsafe) implementations, can be used to formally certify that a constraint system is unsatisfiable.

<2012-10-03 mer.>

<2012-09-12 mer.> Fatima Zohra LEBBAH est actuellement doctorante au laboratoire LITIO de l’Université d’Oran Es-Senia.

Ce travail décrit une approche de résolution locale à population pour appréhender la version quadratique du problème CDO de gestion de portefeuilles bancaires. Le problème du CDO carré provient de l’ingénierie des finances, qui consiste à affecter aux portefeuilles des actifs (ou des titres) qui doivent être variés, permettant ainsi un compromis entre la maximisation du gain et la minimisation du risque de perte. Ce problème est formalisable en termes d’un programme quadratique en nombres entiers, dont les approches de résolution exacte proposées dans la littérature se sont avérées peu performantes quand on augmente le nombre d’actifs et le nombre de portefeuilles. L’échec des méthodes exactes est à l’origine de notre recours à une méthode approchée, à savoir la méthode à population GWW (Go With the Winner). Nous proposons une fonction de voisinage et une fonction objectif dédiées à ce problème. Nous avons réalisé une mise en oeuvre sous l’environnement INCOP, afin de montrer l’intérêt de notre approche sur des instances non triviales du problème.

<2012-06-21 jeu.> Fabien HERMENIER est actuellement maître de conférences dans l’équipe OASIS (INRIA).

The massive amount of resources found in datacenters makes it possible to provide high availability to multi-tier applications. Embedding these applications makes it possible to consolidate them on servers, reducing runtime costs. Nevertheless, replicated VMs have to be carefully placed within the datacenter to provide high availability and good performance. This requires resolving potentially conflicting application and datacenter requirements, while scaling up to the size of modern datacenters. We present BtrPlace, a flexible consolidation manager that is customized through configuration scripts written by the application and datacenter administrators. BtrPlace relies on constraint programming and an extensible library of placement constraints. Scalability is achieved by splitting the datacenter into partitions and computing placements in parallel. Overall, BtrPlace repairs a non-viable placement after a load increase for a 5,000 server datacenter hosting 30,000 VMs with 6,000 constraints in 2 minutes. Using partitions of 2,500 servers, placement computing is reduced to less than 20 seconds.

<2012-02-23 jeu.> Mohamed REZGUI est actuellement doctorant dans l’équipe CeP.

Nous proposons une nouvelle stratégie de recherche (SBS) dans la résolution des CSP (Constraint Satisfaction Problem) pour énumérer toutes les solutions d’un problème. L’idée principale de cette stratégie consiste à énumérer des solutions génériques à partir desquelles toutes les solutions peuvent être efficacement calculées. Les solutions génériques contiennent des valeurs qui sont substituables à toutes les autres. SBS provoque l’apparition des valeurs substituables. Ainsi, à la différence d’une stratégie de recherche classique, SBS économise du temps en générant seulement quelques solutions génériques. Nous montrons expérimentalement que SBS donne des résultats intéressants sur des problèmes ayant un grand nombre de solutions.

<2012-02-23 jeu.> Sophie DEMASSEY est actuellement en visite dans l’équipe CeP.

The Set Covering Problem is one of Karp’s 21 fundamental NP-hard problems and a generic model for many real-world applications solved by linear decomposition. In vehicle routing for instance, the problem is to select a minimum number of routes from a pre-computed set, such that each customer is visited at least once. The best solution methods to date for this problem are lagrangian relaxation-based branch-and-bound. In this presentation, we study how to adapt this approach in a constraint programming (CP) framework. Our goal, in particular, is to derive an optimization method more flexible to the addition of side constraints than the pure linear programming (LP) methods. Three specific aspects are discussed:

• we present a lagrangian-based filtering for the optimization global constraint MinSetCover, or for its famous dual formulation, AtMostNValue;
• we discuss different techniques for improving LP-based branch-and-bound (cost-based branching strategies, primal bounds, dominance cuts) and their adaptation to CP-based branch-and-bound;
• we envisage how to “recompose” applications of Set Covering in compact CP models combining the dynamic generation of the sets with the selection of the minimum cover.

<2011-10-14 ven.> Arnaud Malapert est actuellement post-doctorant dans l’équipe CeP.

Résoudre un problème d’ordonnancement consiste à organiser un ensemble de tâches, c’est-à-dire déterminer leurs dates de début et de fin et leur attribuer des ressources en respectant certaines contraintes. Dans cette thèse, nous proposons de nouvelles approches exactes basées sur la programmation par contraintes pour deux classes de problèmes d’ordonnancement NP-difficiles validées expérimentalement par l’implémentation d’un ensemble de nouvelles fonctionnalités dans le solveur de contraintes choco. Dans un problème d’atelier, n lots sont constitués chacun de m tâches à exécuter sur m machines distinctes. Chaque machine ne peut exécuter qu’une tâche à la fois. La nature des contraintes liant les tâches d’un même lot peut varier (séquencement global ou par lot, pas de séquencement). Le critère d’optimalité étudié est la minimisation du délai total. Nous proposons d’abord une étude et une classification des différents modèles et algorithmes de résolution. Ensuite, nous introduisons une nouvelle approche flexible pour ces problèmes classiques. Une machine à traitement par fournées peut traiter plusieurs tâches en une seule opération, une fournée. Les dates de début et de fin des tâches d’une même fournée sont identiques. Le problème étudié consiste à minimiser le retard algébrique maximal de n tâches de différentes tailles sur une machine de capacité b. Conjointement, la somme des tailles des tâches d’une fournée ne doit pas excéder la capacité b. Nous proposons, dans ce contexte, un modèle basé sur une décomposition du problème. Nous définissons ensuite une nouvelle contrainte pour l’optimisation basée sur une relaxation du problème qui améliore sa résolution.