We consider the resolution of learning problems involving
$\ell_0$-regularization via Branch-and-Bound (BnB) algorithms. These methods
explore regions of the feasible space of the problem and check whether they do
not contain solutions through "pruning tests". In standard implementations,
evaluating a pruning test requires to solve a convex optimization problem,
which may result in computational bottlenecks. In this paper, we present an
alternative to implement pruning tests for some generic family of
$\ell_0$-regularized problems. Our proposed procedure allows the simultaneous
assessment of several regions and can be embedded in standard BnB
implementations with a negligible computational overhead. We show through
numerical simulations that our pruning strategy can improve the solving time of
BnB procedures by several orders of magnitude for typical problems encountered
in machine-learning applications.

通过分支定界（Branch-and-Bound）算法解决涉及 $\ell_0$ 正则化的学习问题，并提出一种用于一类通用的 $\ell_0$ 正则化问题的修剪测试的替代方法，该方法可以同时评估多个区域，在标准分支定界实现中具有可忽略的计算开销，并通过数值模拟表明该修剪策略可以将分支定界过程的求解时间从机器学习应用中常见的典型问题的数量级上提升。

一个新的分支界限修剪框架用于 $l_0$ 正则化问题

A New Branch-and-Bound Pruning Framework for $\ell_0$-Regularized  Problems

The selection of branching variables is a key component of branch-and-bound
algorithms for solving Mixed-Integer Programming (MIP) problems since the
quality of the selection procedure is likely to have a significant effect on
the size of the enumeration tree. State-of-the-art procedures base the
selection of variables on their "LP gains", which is the dual bound improvement
obtained after branching on a variable. There are various ways of selecting
variables depending on their LP gains. However, all methods are evaluated
empirically. In this paper we present a theoretical model for the selection of
branching variables. It is based upon an abstraction of MIPs to a simpler
setting in which it is possible to analytically evaluate the dual bound
improvement of choosing a given variable. We then discuss how the analytical
results can be used to choose branching variables for MIPs, and we give
experimental results that demonstrate the effectiveness of the method on MIPLIB
2010 "tree" instances where we achieve a 5% geometric average time and node
improvement over the default rule of SCIP, a state-of-the-art MIP solver.

本文提出了一种基于理论模型的枝界算法，其用于选择分支变量的方法是对 MIP 问题进行简化后，对选择不同变量可以得到对偶理论的提升（LP gains）的解析式进行计算，并提出了该方法在实验中的有效性。