We consider the problem of learning optimal binary classification trees.
Literature on the topic has burgeoned in recent years, motivated both by the
empirical suboptimality of heuristic approaches and the tremendous improvements
in mixed-integer programming (MIP) technology. Yet, existing approaches from
the literature do not leverage the power of MIP to its full extent. Indeed,
they rely on weak formulations, resulting in slow convergence and large
optimality gaps. To fill this gap in the literature, we propose a flow-based
MIP formulation for optimal binary classification trees that has a stronger
linear programming relaxation. Our formulation presents an attractive
decomposable structure. We exploit this structure and max-flow/min-cut duality
to derive a Benders' decomposition method, which scales to larger instances. We
conduct extensive computational experiments on standard benchmark datasets on
which we show that our proposed approaches are 50 times faster than
state-of-the art MIP-based techniques and improve out of sample performance up
to 13.8%.

该研究提出了一种基于流的 MIP 公式，利用 Bender's 分解方法解决最优二元分类树问题，该方法比现有的 MIP 技术快 50 倍，并在标准基准数据集上将预测精度提高多达 13.8%。