Reference : A combinatorial branch-and-bound algorithm for box search
Scientific journals : Article
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/168096
A combinatorial branch-and-bound algorithm for box search
English
Mathieu, Sébastien mailto [Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète >]
Louveaux, Quentin mailto [Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète >]
2014
Discrete Optimization
Elsevier
13
36-48
Yes
International
1572-5286
1873-636X
[en] Box search ; Combinatorial optimization ; Data mining ; Branch-and-bound ; Mixed Integer Linear Programming
[en] 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 that this approach competes with current state of the art mixed-integer solvers.
The algorithm proposed in this paper may be seen as a simple and dependence-free method to solve the box search problem.
Service public de Wallonie
Virtuoso
Researchers ; Professionals ; Students ; Others
http://hdl.handle.net/2268/168096
10.1016/j.disopt.2014.05.001

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
boxsearch-2013-mathieu.pdfAuthor preprint441.06 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.