Thursday 27
Non-linear optimisation, bi-level optimisation and yield management
Claudia D'Ambrosio
› 11:30 - 12:00 (30min)
› Bât. A - TD 34
Quadratic combinatorial optimization using separable underestimators
Emiliano Traversi  1@  , Christoph Buchheim  2  
1 : Laboratoire d'Informatique de Paris-Nord  (LIPN)  -  Website
Université Paris XIII - Paris Nord, CNRS : UMR7030, Institut Galilée
Institut Galilée 99, avenue J.B Clément 93430 VILLETANEUSE -  France
2 : TU Dortmund, Fakultät für Mathematik
Vogelpothsweg 87 44227 Dortmund -  Allemagne

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


Online user: 2