2015

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	A branch-and-cut-and-price algorithm for the green vehicle routing problem with partial recharges and multiple technologies
Description:	Alberto Ceselli Abstract: We tackle a variation of the vehicle routing problem in which the transportation fleet is composed of electric vehicles with limited autonomy in need for recharge during the execution of their duties. Different technologies can be chosen at each station, offering different trade-off between recharge cost and time. We present an algorithm exploiting column generation, cutting planes and branch-and-bound for the exact solution of the problem. The pricing phase requires elementary resource constrained shortest path problems to be solved, and is carried out with both heuristics and an exact dynamic programming routine. The cut separation phase is performed by running heuristics from the literature on a particular support graph. Experiments on benchmark instances from the VRP literature reveal that our algorithm is effective in solving instances with up to thirty customers, nine recharge stations, five vehicles and three technologies to optimality.

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	The Johnson-Lindenstrauss Lemma in Linear and Integer Feasibility
Description:	Leo Liberti The Johnson-Lindenstrauss lemma allows dimension reduction on real vectors with low distortion on their pairwise Euclidean distances. This result is often used in algorithms such as $k$-means or $k$ nearest neighbours since they only use Euclidean distances, and has sometimes been used in optimization algorithms involving the minimization of Euclidean distances. In this paper we introduce a first attempt at using this lemma in the context of feasibility problems in linear and integer programming, which cannot be expressed only in function of Euclidean distances. Leo Liberti, Vu Khac Ky, Pierre-Louis Poirion CNRS LIX, Ecole Polytechnique, Palaiseau, France

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Identités de Gallai chromatiques opérant sur la fonction Theta Lovasz
Description:	Denis Cornaz Un paramètre de graphe (une fonction qui associe un entier à tout graphe) est dit sandwich si, pour tout graphe, il est compris entre la taille de la clique maximum et le nombre chromatique. Nous définissons à l'aide d'un graphe auxiliaire (un sous-graphe partiel du line-graphe) un opérateur PHI qui transforme tout paramètre sandwich en un autre paramètre sandwich. Nous montrons que PHI améliore la qualité des bornes polynomiales pour la coloration (bornes obtenues par la programmation semie-définie), de plus, expérimentalement, l'amélioration est significative. Par ailleurs, PHI détériore la qualité de la borne obtenue par la programmation linéaire.