2014

Heure:	12:00 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Branch-and-Price for the relaxed clique Partitioning and Covering Problems
Description:	Roberto Wolfler Calvo Relationships between objects can be modeled with graphs, where nodes represent the different objects and edges express the relationship. Social network analysis is an example where clusters, e.g., formed by members of a community, are studied using cliques and clique relaxations. A clique is a subgraph with pairwise directly connected nodes, i.e., a subgraph with diameter one. Several relaxations have been defined either in terms of distance (k-clique), degree (k-plex, k-core), diameter (k-club), or density. The majority of the literature deals with identifying such subgraphs of maximum cardinality or weight. In this presentation, we consider the generic problem of covering or partitioning a graph with a set of relaxed cliques. We present an exact solution fromework for solving the relaxed clique partitioning and covering problems based on branch-and-price. Herein, the subproblem consists of finding a relaxed clique of maximum weight. We present heuristics and a new combinatorial branch-and-bound algorithm for its resolution. This is a join work with Fabio Furini and Stefan Irnic.

Heure:	12:00 - 13:00
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Lexicographical polytopes
Description:	Michele Barbato Within a fixed integer box of R^n, the lexicographical polytopes are the convex hulls of the integer points that are lexicographically between two given integer points. We prove that, together with the bounds, the linear inequalities that arise naturally when characterizing those points suffice to describe these polytopes. As a consequence, this family of integer polytopes is closed by intersection. Beside, we prove that lexicographical polytopes are precisely the superincreasing knapsacks described by Gupte. Our contribution is to provide significantly simpler and shorter proofs. This is a joint work with Roland Grappe, Mathieu Lacroix and Clément Pira.

Heure:	12:00 - 13:00
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Vérification distribuée par exploration d'un espace de paramètres
Description:	Camille Coti Dans cet exposé, je présenterai un travail effectué avec Étienne André et Sami Evangelista portant sur la parallélisation d'un algorithme de vérification par exploration d'un espace de paramètres dans le but d'établir un ensemble de contraintes. Ces contraintes forment un pavage de cet espace de paramètres par des polyèdres irréguliers. La parallélisation de cette exploration ne peut alors pas s'effectuer en utilisant une décomposition de domaine classique, du fait du caractère irrégulier des polyèdres obtenus. Nous avons implémenté et évalué deux heuristiques de décomposition du calcul entre les processus parallèles et examiné leurs performances. Ce travail a été présenté à la conférence EuroMPI/Asia 2014.