Mardi 12 Novembre
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 branchandcut 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) 
Mardi 19 Novembre
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. 
Mardi 26 Novembre
Heure: 
12:00  13:30 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
On unified methods for multiattribute 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, multiperiod 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 problemtailored development. 
Vendredi 29 Novembre
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 nondegenerate pivots only, the Dynamic Constraints Aggregation method for the set partitioning problem, and the strongly polynomial Minimum Mean CycleCancelling algorithm for the capacitated network flow problem. 
Mardi 3 Décembre
Heure: 
12:00  13:30 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
A branchandbound method for box constrained integer polynomial optimization 
Description: 
Claudia D'Ambrosio We consider the problem of minimizing an arbitrary polynomial subject to box and integrality constraints. We propose a new class of underestimators composed of separable functions of the original variables and use it within a branchandbound scheme to easily and quickly compute lower bounds. Computational results on randomly generated instances show good performance with respect to the ones of different opensource solvers like Couenne, Gloptipoly , and SCIP. Moreover, the second part of the talk will be devoted to present a different perspective on partially separable problems. In particula, an exact algorithm for mixed integer nonlinear programming problems with separable nonconvexities will be presented. 
Mardi 17 Décembre
Heure: 
12:00  13:30 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
Konig's edgecolouring theorem for all graphs 
Description: 
Denis Cornaz We show that the maximum degree of a graph G is equal to the minimum number of ocm sets covering G, where an ocm set is the vertexdisjoint union of elementary odd cycles and one matching, and a collection of ocm sets covers G if every edge is in the matching of an ocm set or in some odd cycle of at least two ocm sets. This minmax relation gives a linear description of the star polytope with a minimal TDIsystem. Joint work with V. H. Nguyen from LIP6. 

