|
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. |
Mardi 3 Décembre
| Heure: |
12:00 - 13:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
A branch-and-bound 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
under-estimators composed of separable functions of the original variables
and use it within a branch-and-bound scheme to easily and quickly compute
lower bounds. Computational results on randomly generated instances show
good performance with respect to the ones of different open-source 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 non-linear programming problems with
separable non-convexities 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 edge-colouring 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 vertex-disjoint 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 min-max relation gives a linear description of the star
polytope with a minimal TDI-system.
Joint work with V. H. Nguyen from LIP6. |
|
|
