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