|
|
Mardi 5 Février
Heure: |
12:30 - 13:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Separable non-convex underestimators for binary quadratic programming |
Description: |
Emiliano Traversi We present a new approach to constrained quadratic binary programming. Dual bounds are computed by choosing appropriate global underestimators of the objective function that are separable but not necessarily convex. Using the binary constraint on the variables, the minimization of this separable underestimator can be reduced to a linear minimization problem over the same set of feasible vectors. For most combinatorial optimization problems, the linear version is considerably easier than the quadratic version. We explain how to embed this approach into a branch-and-bound algorithm and present experimental results. |
Mardi 19 Février
Heure: |
12:30 - 13:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Discrete optimization using semidefinite methods |
Description: |
Angelika Wiegele Many real-world applications, although being non-linear, can be well described by linearized models. Therefore, Linear Programming (LP) became a widely studied and applied technique in many areas of science, industry and economy. Semidefinite Programming (SDP) is an extension of LP. A matrix-variable is optimized over the intersection of the cone of positive semidefinite matrices with an affine space. It turned out, that SDP can provide significantly stronger practical results than LP. Since then SDP turned out to be practical in a lot of different areas, like combinatorial optimization, control theory, engineering, and more recently in polynomial optimization.
In this talk I will present some ideas how to model discrete optimization problems using semidefinite programming in order to obtain semidefinite relaxations. Some of this relaxations proved to be succesful when using in a branch-and-bound framework. Furthermore, I want to present a new idea of how to strengthen semidefinite relaxations.  |
Mardi 26 Février
Heure: |
12:30 - 13:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
 Réservation de voies dans un réseau de transport |
Description: |
Feng Chu |
|
|