A Scalable MIP-based Method for Learning Optimal Multivariate Decision
  Trees
  Several recent publications report advances in training optimal decision
trees (ODT) using mixed-integer programs (MIP), due to algorithmic advances in
integer programming and a growing interest in addressing the inherent
suboptimality of heuristic approaches such as CART. In this paper, we propose a
novel MIP formulation, based on a 1-norm support vector machine model, to train
a multivariate ODT for classification problems. We provide cutting plane
techniques that tighten the linear relaxation of the MIP formulation, in order
to improve run times to reach optimality. Using 36 data-sets from the
University of California Irvine Machine Learning Repository, we demonstrate
that our formulation outperforms its counterparts in the literature by an
average of about 10% in terms of mean out-of-sample testing accuracy across the
data-sets. We provide a scalable framework to train multivariate ODT on large
data-sets by introducing a novel linear programming (LP) based data selection
method to choose a subset of the data for training. Our method is able to
routinely handle large data-sets with more than 7,000 sample points and
outperform heuristics methods and other MIP based techniques. We present
results on data-sets containing up to 245,000 samples. Existing MIP-based
methods do not scale well on training data-sets beyond 5,500 samples.
