|
|
 |
|
Mardi 8 Avril
| Heure: |
12:00 - 13:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Split Cuts and Separable Underestimator for non-convex quadratic problems |
| Description: |
Emiliano Traversi In this work we investigate the computational potential of two tools
for solving non-convex quadratic problems: split inequalities and
separable underestimator.
Split inequalities were first introduced by Letchford and further
examined by Burer and Letchford. For small instances with
box-constraints, we show that the resulting dual bounds are very
tight.The gap can be further decreased by separating so-called
non-standard split inequalities, which we examine in the case of ternary variables.Separable
underestimator are used for solving constrained quadratic binary
programming. Dual bounds are computed by choosing appropriate
underestimators of the objective function that are separable but not
necessarily convex. We explain how to embed this approach into a
branch-and-bound algorithm and present experimental results for several
classes of combinatorial optimization problems, including the quadratic
shortest path problem, for which we provide the first exact approach
available in the literature. |
|
|
