Reproduce “Strong Optimal Classification Trees” on OpenResearch

About this paper

Sina Aghaei, Andrés Gómez, Phebe Vayanos

Researchers at the University of Southern California (USC) developed a new mixed-integer optimization framework and a tailored Benders' decomposition method that significantly improve the efficiency of learning optimal classification trees. This approach achieves up to 51x speedups and up to 51% higher out-of-sample accuracy compared to prior MIO methods, addressing numerical instability issues and supporting fairness and interpretability constraints.

Key insights

• A flow-based Mixed-Integer Optimization (MIO) formulation for optimal classification trees yields a provably stronger Linear Optimization (LO) relaxation than existing methods, leading to tighter bounds and faster convergence.
• A tailored Benders' decomposition method, coupled with a specialized min-cut procedure, efficiently solves subproblems and generates facet-defining cuts, accelerating the MIO solution process.
• The expressive power of the MIO framework allows for seamless integration of practical side constraints, including those for imbalanced datasets (e.g., optimizing balanced accuracy) and various fairness notions (e.g., statistical parity, equalized odds).

Summary by alphaXiv.