Random Forest-driven Heuristic for Margin Optimal Regression Trees

This report introduces two heuristic approaches designed to generate high-quality feasible solutions for an Optimal Margin Regression Tree (MARGOT-reg) formulated as a Mixed Integer Quadratic Programming (MIQP) problem. MARGOT-reg aims to combine the interpretability of decision trees with the strong generalization capabilities of Support Vector Regression (SVR), and it takes inspiration from MARGOT for classification. The proposed framework offers a promising balance between interpretability, predictive accuracy, and model robustness, contributing to the integration of exact optimization methods and machine learning approaches for regression tasks. The first proposed heuristic, the Local SVR Heuristic, employs a recursive top-down strategy that applies weakened SVR models at branch nodes and powerful SVR models at leaf nodes. The second one, the Proximity Heuristic, leverages Random Forest-derived proximity matrix to introduce constraints that enforce the grouping of samples with high proximity values between them. Both heuristics aim to efficiently warm-start the optimization process in order to enhance the performance of an off-the-shelf branch-and-bound solver used to solve the MIQP problem. Empirical results on multiple benchmark datasets demonstrate that both heuristics provide high-quality initial solutions that can improve the performance of the branch-and-bound solver, with the Proximity Heuristic yielding superior reductions in the objective function.