Branch-and-bound algorithm applied to sparse optimization problems: a study of some exploration strategies

Gwenael Samain (1, 2) , Jordan Ninin (3, 4) , Sébastien Bourguignon (1, 2)

1 LS2N - Laboratoire des Sciences du Numérique de Nantes
2 ECN - École Centrale de Nantes
3 Lab-STICC_MATRIX - Equipe Models and AlgoriThms for pRocessIng and eXtracting information
4 ENSTA Bretagne - École Nationale Supérieure de Techniques Avancées Bretagne

Sparse optimization focuses on finding a solution to least-squares problems with few non-zero components. Applications include inverse problems in signal processing, subset selection, or portfolio optimization. Optimization problems can be formulated as mixed-integer programs. A dedicated branchand-bound algorithm is able to exploit the specific structure of such problems and finds the global minimum much faster than generic MIP solvers. We will present some results about the fine-tuning process of this branch-and-bound algorithm, focusing mainly on the exploration strategy.

Domaines: Recherche opérationnelle [math.OC]; Optimisation et contrôle [math.OC]; Traitement du signal et de l'image [eess.SP]

Gwenael Samain, Jordan Ninin, Sébastien Bourguignon. Branch-and-bound algorithm applied to sparse optimization problems: a study of some exploration strategies. EUROPT 2021, the 18th international workshop on continuous optimization, continuous optimization working group of EURO (The Association of European Operational Research Societies)., Jul 2021, Toulouse, France. ⟨hal-03474817⟩