27 Avril - 3 Mai

Retour à la vue des calendrier
Mardi 28 Avril
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Exact Algorithms for Nonconvex Quadratic Integer Optimization
Description: Christoph Buchheim The talk addresses the problem of minimizing a quadratic objective function over integer variables. Even in the most simple case of binary or box-constrained integer variables, such problems are very hard to solve in theory and in practice. In fact, the problem remains NP-hard both in the case of a convex objective function over binary variables (then being equivalent to max-cut) and in the case of a non-convex objective function over the unit cube (the so-called BoxQP).

After shortly reviewing some classical approaches for quadratic discrete optimization, we present two recent methods that are specifically designed for the nonconvex case, aiming at relaxations that jointly address the nonconvexity of the objective function and the nonconvexity of the discrete variable domains. While the first approach results in a semidefinite relaxation of the problem, the second approach uses ellipsoidal relaxations; both approaches can be embedded into branch-and-bound schemes. We present experimental results for the resulting algorithms, showing that the SDP-based approach yields very strong dual bounds that however take more time to be computed, while the second approach based on ellipsoidal relaxations is able to enumerate a large number of nodes in a short time due to a sophisticated preprocessing phase. The resulting total running times are comparable; both approaches however significantly outperform standard software such as Couenne or BARON.