2013

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Programmation linéaire colorée
Description:	Pauline Sarrabezolles Considérons d + 1 ensembles de points de R^d en position générique, et attribuons à chacun des ces ensembles une couleur distincte. D'après le théorème de Carathéodory coloré, prouvé par Imre Barany en 1982, si un point est contenu dans l'enveloppe convexe de chacun de ces ensembles, alors il est contenu dans l'enveloppe convexe d'un simplexe formé d'un point de chaque couleur. Un tel simplexe est dit arc-en-ciel. La conjecture de la profondeur simpliciale colorée, formulée par Antoine Deza et ses coauteurs en 2006, dit qu'un tel point est en fait contenu dans au moins d^2 + 1 simplexes arc-en-ciel, ce qui a été vérifié par différents auteurs pour d = 1, 2 et 3. Nous vérifions cette conjecture en dimension 4 et améliorons les bornes connues dans les dimensions plus élevées. Ces résultats sont obtenus grâce à une généralisation combinatoire des configurations colorées de points, suggérée par Imre Barany : les systèmes octaédriques. Nous présentons de plus des algorithmes résolvant divers problèmes de programmation linéaire colorée.

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Disjunctive conic cuts for mixed integer convex optimization
Description:	Pietro Belotti We study the convex hull of the intersection of a convex set E and a linear disjunction, which is at the core of solution techniques for Mixed Integer Conic Optimization. We prove that if there exists a cone K that has the same intersection with the boundary of the disjunction as E, then the convex hull is the intersection of E with K. The existence of such a cone is difficult to prove for general conic optimization. However, for the special case of Mixed Integer Second Order Cone Optimization (MISOCO), such a cone can be efficiently generated. This cone provides a conic cut for MISOCO that can be used effectively in branch-and-cut algorithms for MISOCO problems. We show some preliminary computational results that substantiate our claims. (Joint work with Julio C. Goez, Imre Polik, Ted K. Ralphs, Tamas Terlaky)

Heure:	12:00 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Line graphs and Facility Location Problem
Description:	Laurent Beaudou (This is a joint work with M. Baïou, Z. Li and V. Limouzy) The line graph of a digraph can be defined in a few different ways. One  of them came naturally from our study of a facility location problem. We discuss the complexity of recognizing such graphs and their cousins. During this seminar, we shall also have an overview of the historical birth  of facility location problems.

Heure:	12:00 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	On unified methods for multi-attribute VRPs, route evaluation operators and large neighborhoods
Description:	Thibaut VIDAL The research on heuristics for VRP has been historically articulated around several streams of research dedicated to some major problem variants, e.g. with time windows, multiple depots, multi-period deliveries. Such diverse research lines are justified if the nature of problems calls for drastically different approaches. However, VRP variants share naturally many common aspects, and many specific heuristic strategies may be applicable to a broader range of problems. The identification of fundamental resolution strategies is thus of primary concern to progress towards more unified VRP algorithms, providing the means to address various application cases in a timely manner without extensive problem-tailored development.

Heure:	12:00 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Vector space decomposition for linear programming
Description:	Jacques Desrosiers This presentation describes a vector space decomposition algorithm for a linear program with bounded variables. Given a current feasible solution, the exchange mechanism towards the next one is split into independent parts based on two orthogonal vector subspaces, that is, the master and the subproblem ones. The subproblem generates directions (rays) compatible with the vector subspace of the master problem. Indeed the subproblem partially satisfies the exchange mechanism that is completed at the master level. Special cases of this generic vector space decomposition algorithm are, amongst others, the Primal Simplex, the Improved Primal Simplex yielding non-degenerate pivots only, the Dynamic Constraints Aggregation method for the set partitioning problem, and the strongly polynomial Minimum Mean Cycle-Cancelling algorithm for the capacitated network flow problem.