Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Techniques for accelerating Branch-and-Bound algorithms dedicated to sparse optimization

Abstract : Sparse optimization-fitting data with a low-cardinality linear model-is addressed through the minimization of a cardinality-penalized least-squares function, for which dedicated branch-and-bound algorithms clearly outperform generic mixed-integerprogramming solvers. Three acceleration techniques are proposed for such algorithms. Convex relaxation problems at each node are addressed with dual approaches, which can early prune suboptimal nodes. Screening methods are implemented, which fix variables to their optimal value during the node evaluation, reducing the subproblem size. Numerical experiments show that the efficiency of such techniques depends on the node cardinality and on the structure of the problem matrix. Last, different exploration strategies are proposed to schedule the nodes. Best-first search is shown to outperform the standard depth-first search used in the related literature. A new strategy is proposed which first explores the nodes with the lowest least-squares value, which is shown to be the best at finding the optimal solution-without proving its optimality. A C++ solver with compiling and usage instructions is made available.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Gwenaël Samain Connect in order to contact the contributor
Submitted on : Friday, May 6, 2022 - 4:03:40 PM
Last modification on : Friday, August 5, 2022 - 2:54:52 PM
Long-term archiving on: : Sunday, August 7, 2022 - 7:19:58 PM


Files produced by the author(s)


  • HAL Id : hal-03661177, version 1


Gwenaël Samain, Sébastien Bourguignon, Jordan Ninin. Techniques for accelerating Branch-and-Bound algorithms dedicated to sparse optimization. 2022. ⟨hal-03661177⟩



Record views


Files downloads