A Polyhedral Study of Multivariate Decision Trees

Decision trees are a widely used tool for interpretable machine learning. Multivariate decision trees employ hyperplanes at the branch nodes to route datapoints throughout the tree and yield more compact models than univariate trees. Recently, mixed-integer programming (MIP) has been applied to formulate the optimal decision tree problem. A key component of most MIP formulations is a specification of how to route datapoints in the tree from the root to the leaves. Our goal is to provide polyhedral characterizations of realizable routings, that is, routings that can be realized using multivariate branching rules. We first focus on shattering inequalities, a class of valid inequalities that can be used to strengthen almost any MIP formulation and that have been shown to be computationally effective. We prove that if all the feature vectors are in general position, then the shattering inequalities defined for the root of the tree are facet defining for the convex hull of the realizable routings. We then show that every facet-defining inequality of a depth one tree involving at least two variables is also facet defining for trees of arbitrary depth. Finally, we show that facet-defining inequalities characterizing realizable routings are also facet-defining for a complete MIP formulation. We validate our theoretical results by performing numerical experiments that specifically exploit shattering inequalities defined at the root node and we observe an improvement in performance for both numerical and categorical data sets, especially for decision trees of intermediate size. Funding: C. Michini gratefully acknowledges funding from the DoD, Air Force [Award FA9550-23-1-0487].