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