CP @ I3S

Table of Contents

Berthe Y. CHOUERY : Localizing & Bolstering Constraint Propagation in a Tree Decomposition

<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.

Rita MACEDO : aggregation and disaggregation in network flow models

<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.

Radoslaw CYMER : applications of Matching Theory in Constraint Programming

<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.

Stefano DI ALESIO : a Constraint Program for Software Performance Analysis and Testing

<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.

Éric GOUBAULT : analyse de robustesse en précision finie

<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.

Chu Min LI : sur les interactions entre le problème MaxClique et le CSP.

<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é.

Visite de Yahah Lebbah (université d'Oran ES-SENIA).

<2013-05-30 jeu.>

Mohamed Said BELAID : solveur de contraintes sur les nombres flottants.

Mohamed Said BELAID est actuellement doctorant à l'I3S.

Les méthodes de vérification et de test basées sur la programmation par contraintes sont peu appliquées sur les programmes avec des opérations à virgule flottante. Une des raison est l'absence d'un solveur efficace capable de fournir des solutions exactes sur les flottants. Nous présentons dans cet article une nouvelle méthode qui fournit des solutions sur les nombres flottants. Cela peut être utile pour générer des cas de tests ou pour générer des contre-exemples. Notre méthode a été testée sur des programmes qui montrent l'intérêt d'un solveur spécifique sur les flottants.

Amina KEMMAR : an interval based approach for graph-mining.

Amina KEMMAR est actuellement doctorante à l'université d'Oran ES-SENIA.

The canonical encoding is one of the key operations required by subgraph mining algorithms for the candidate generation. Existing approaches make use of canonical encodings with an exponential time complexity and are more expensive for dense graph databases. In this paper, we propose to relax the canonicity of the encoding, and get encodings with a polynomial time complexity allowing to generate either a significant subset of frequent subgraphs or all subgraphs with duplicates. These encodings, which we call lower-encoding and upper-encoding respectively, are implemented in the third step of the state of the art Gaston miner to encode cyclic graphs. Experiments show that the lower-encoding is efficient when the graph database as well as the frequent cyclic subgraphs are dense.

Noureddine ARIBI : approches d'élicitation basées sur le coefficient de Spearman pour l'optimisation multicritère par ordre lexicographique.

Noureddine ARIBI est actuellement doctorant à l'université d'Oran ES-SENIA.

Nous étudions l'exploitation du coefficient de corrélation rho de Spearman pour résoudre le problème d'élicitation des paramètres de l'opérateur multicritère d'ordre lexicographique (LO). Une première exploitation du coefficient statistique rho de Spearman consiste à l'utiliser comme une méthode heuristique. Une deuxième exploitation propose l'intégration de ce coefficient statistique dans deux méthodes exactes basées respectivement sur la programmation par contraintes et sur la programmation en nombres entiers. Comme toutes les méthodes d'optimisation multicritères, la méthode LO a un paramètre qui doit être fixé avec soin, soit pour déterminer la solution optimale (meilleur compromis) ou pour classer l'ensemble des solutions faisables (alternatives). C'est pourquoi nous proposons des méthodes d'élicitation afin d'assister le décideur (DM) à fixer ces paramètres. Ces méthodes nécessitent des connaissances préalables, que le DM peut proposer facilement. Nous présentons une étude expérimentale montrant l'efficacité de nos approches.

Séminaire commun CeP-Coati

<2013-01-21 lun.>

Frédéric GIROIRE : energy-efficient management of Telecom Networks.

Frédéric GIROIRE est actuellement chargé de recherche CNRS dans l'équipe Coati

Several studies exhibit that the traffic load of the routers only has a small influence on their energy consumption. Hence, the power consumption in networks is strongly related to the number of active network elements, such as interfaces, line cards, base chassis,… The goal thus is to find a routing that minimizes the (weighted) number of active network elements used when routing. In this study, we consider a simplified architecture where a connection between two routers is represented as a link joining two network interfaces. When a connection is not used, both network interfaces can be turned off. Therefore, in order to reduce power consumption, the goal is to find the routing that minimizes the number of used links while satisfying all the demands. We first define formally the problem and we model it as an integer linear program. Then, we prove that this problem is not in APX, that is there is no polynomial-time constant-factor approximation algorithm. We propose a heuristic algorithm for this problem and we also prove some negative results about basic greedy and probabilistic algorithms. Thus we present a study on specific topologies, such as trees, grids and complete graphs, that provide bounds and results useful for real topologies. We then exhibit the gain in terms of number of network interfaces (leading to a global reduction of approximately 33 MWh for a medium-sized backbone network) for a set of existing network topologies: we see that for almost all topologies more than one third of the network interfaces can be spared for usual ranges of operation. Finally, we discuss the impact of energy efficient routing on the stretch factor and on fault tolerance.

Issam TAHIRI : robust metric inequalities for the Γ-Robust network loading problem.

Issam TAHIRI est actuellement doctorant à l'INRIA dans l'équipe Coati.

In this study, we consider the network loading problem under demand uncertainties with static routing, i.e, a single routing scheme based on the fraction of the demands has to be determined. We generalize the class of metric inequalities to the Γ-robust setting and show that they yield a formulation in the capacity space. We describe a polynomial time exact algorithm to separate violated robust metric inequalities as model constraints. Moreover, rounded and tight robust metric inequalities describing the convex hull of integer solutions are presented and separated in a cut- and-branch approach. Computational results using real-life telecommunication data demonstrate the major potential of (tight) robust metric inequalities by considering the integrality gaps at the root node and the overall optimality gaps. Speed-up factors between 2 and 5 for the compact flow and between 3 and 25 for the capacity formulation have been achieved by exploiting robust metric inequalities in the solving process.

Arnaud MALAPERT : the package server location problem.

Arnaud MALAPERT est actuellement maître de conférences à l'UNS dans l'équipe CeP.

We introduce a new multi-objective optimization problem derived from a real-world application: the package server location problem. A number of package servers are to be located at nodes of a network. Demand for these package servers is located at each node, and a subset of nodes are to be chosen to locate one or more package servers. Each client is statically associated to a package server. The objective is to minimize the number of package servers while maximizing the efficiency and the reliability of the broadcast of packages to clients. These objectives are contradictory: the broadcast becomes more efficient as the number of servers increases. This problem is analyzed as a multi-objective optimization problem and aa mathematical formulation is proposed. In addition, the criteria combination can be specified via a small dedicated language. Results for exact multi-objective solution approaches based on mixed integer linear programming are reported.

Olivier PONSINI : stratégies de recherche pour le model-checking borné basées sur la programmation par contraintes

Olivier PONSINI actuellement ingénieur de recherche dans l'équipe CeP.

Cette présentation introduira l'activité de l'équipe CeP autour de la vérification des systèmes. Nous nous intéresserons à la vérification des spécifications des programmes impératifs. Nous avons développé une approche de model-checking borné qui s'appuie sur la programmation par constraintes. Dans ce cadre, nous avons défini plusieurs stratégies d'exploration du graphe de flot de contrôle d'un programme. Nous présenterons deux de ces stratégies ainsi que l'outil CPBPV qui les supporte.

Catherine DUBOIS : un solveur CSP(FD) vérifié formellement.

<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.

Répétition générale avant CP 2012

<2012-10-03 mer.>

Mohamed REZGUI : a search strategy based on substitutability.

Mohamed REZGUI est actuellement doctorant dans l'équipe CeP.

We introduce a new search strategy for enumerating all solutions of a constraint satisfaction problem. This strategy enumerates generic solutions from which all solutions can be efficiently computed. Generic solutions contain substitutable values, that can be replaced by other values in order to generate the set of all solutions. Our strategy favours the appearance of these substitutable values. Consequently, it may save time by generating less generic solutions than solutions. We give some experimental results showing the advantage of this new search for binary CSPs with extensional constraints.

Mohammed Said BELAID : boosting local consistency algorithms over floating-point numbers.

Mohammed Said BELAID est actuellement ATER dans l'équipe CeP.

Solving constraints over floating point numbers is a critical issue in numerous applications notably in program verification. Capabilities of constraints over the floating point numbers that are required to reason correctly on numerical programs have been so far limited to 2b-consistency and its derivatives. Though safe, such filtering techniques suffer from the well known pathological problems of local consistencies, e.g., inability to handle efficiently multiple occurrences of the variables. These limitations also take roots in the strongly restricted floating point arithmetic. To circumvent the poor properties of floating point arithmetic, we propose in this paper to build various relaxations over the reals of the problem over the floats. We show that using LP to solve a linearisation of such relaxations can be very effective for boosting filtering techniques for constraints over the floats. Preliminary experiments on a limited but relevant set of benchmarks are very promising.

Olivier PONSINI : refining abstract interpretation based value analysis with constraint programming techniques.

Olivier PONSINI est actuellement ingénieur de recherche dans l'équipe CeP.

Abstract interpretation based value analysis is a classical approach for verifying programs with floating-point computations. However, state-of-the-art tools compute an over-approximation of the variable values that can be very coarse. In this paper, we show that constraint solvers can significantly refine the approximations computed with abstract interpretation tools. We introduce a hybrid approach that combines abstract interpretation and constraint programming techniques in a single static and automatic analysis. The system we developed is substantially more precise than state-of-the-art static analysers.

Fatima Zohra LEBBAH : approches de résolution du problème CDO carré (square Collateralized Debt Obligations).

<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.

Fabien HERMENIER : autonomous and flexible management of virtual machines in hosting platforms.

<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.

Mohamed REZGUI : une stratégie de recherche basée sur la substituabilité.

<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.

Sophie DEMASSEY : constraint-based Optimization for Set Covering.

<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.

Arnaud MALAPERT : techniques d'ordonnancement d'atelier et de fournées basées sur la programmation par contraintes.

<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.

Created: 2017-08-02 mer. 12:08