Return to Colloquia & Seminar listing
A combinatorial branch-and-bound algorithm for box search
Optimization| 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.