Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

A combinatorial branch-and-bound algorithm for box search


Speaker: Quentin Louveaux, Universite de Liege, Belgium
Location: 0 MSB
Start time: Mon, Sep 9 2013, 2:10PM

Considering a set of points in a multi-dimensional space with an associated real value for each point, we want to find the box with the maximum sum of the values of the included points. This problem has applications in data mining and can be formulated as a mixed-integer linear program. We propose a branch-and-bound algorithm where the bounding is obtained by combinatorial arguments instead of the traditional linear relaxation. Computational experiments show the practicality of the approach whereas the mixed-integer programming formulation faces some numerical issues. This is a joint work with SĂ©bastien Mathieu.