  Decision trees have been a very popular class of predictive models for
decades due to their interpretability and good performance on categorical
features. However, they are not always robust and tend to overfit the data.
Additionally, if allowed to grow large, they lose interpretability. In this
paper, we present a mixed integer programming formulation to construct optimal
decision trees of a prespecified size. We take the special structure of
categorical features into account and allow combinatorial decisions (based on
subsets of values of features) at each node. Our approach can also handle
numerical features via thresholding. We show that very good accuracy can be
achieved with small trees using moderately-sized training sets. The
optimization problems we solve are tractable with modern solvers.
