EURO 2025 Leeds
Abstract Submission

2928. Leveraging Support Vector Machines to construct Margin Optimal Decision Trees

Invited abstract in session TB-3: Young Women 4OR - 2, stream WISDOM - Women in OR.

Tuesday, 10:30-12:00
Room: Esther Simpson 1.01

Authors (first author is the speaker)

1. Marta Monaci
Institute for System Analysis and Computer Science "Antonio Ruberti" (IASI), National Research Council of Italy

Abstract

In recent years, there has been growing interest in interpretable machine learning models that provide explanatory insights into their decision-making process. In this context, thanks to their inherent interpretability, decision tree methods have been extensively studied for classification and regression tasks. While traditional approaches to building decision trees rely on greedy heuristics, the remarkable advances in mixed-integer programming (MIP) over the last decades have led to the formulation of various MIP models for training optimal decision trees. Along this research line, we introduce Margin Optimal Trees, a class of optimal trees that embed margin-based multivariate hyperplanes nested in a binary tree structure. We first present a quadratic mixed-integer formulation that leverages the generalization capabilities of Support Vector Machines for binary classification and then discuss variants of the proposed model. The formulation relies on big-M constraints, which lead to a weak continuous relaxation that limits the method's scalability on large instances. To improve the computational performance of the proposed method, we investigate a tailored algorithmic approach that exploits the decomposable structure of the problem. Finally, we evaluate the method on benchmark datasets to assess its computational efficiency and generalization capabilities.

Keywords

Status: accepted

Back to the list of papers