  This paper explores the use of Column Generation (CG) techniques in
constructing univariate binary decision trees for classification tasks. We
propose a novel Integer Linear Programming (ILP) formulation, based on
root-to-leaf paths in decision trees. The model is solved via a Column
Generation based heuristic. To speed up the heuristic, we use a restricted
instance data by considering a subset of decision splits, sampled from the
solutions of the well-known CART algorithm. Extensive numerical experiments
show that our approach is competitive with the state-of-the-art ILP-based
algorithms. In particular, the proposed approach is capable of handling big
data sets with tens of thousands of data rows. Moreover, for large data sets,
it finds solutions competitive to CART.
