  Global optimization of decision trees has shown to be promising in terms of
accuracy, size, and consequently human comprehensibility. However, many of the
methods used rely on general-purpose solvers for which scalability remains an
issue. Dynamic programming methods have been shown to scale much better because
they exploit the tree structure by solving subtrees as independent subproblems.
However, this only works when an objective can be optimized separately for
subtrees. We explore this relationship in detail and show the necessary and
sufficient conditions for such separability and generalize previous dynamic
programming approaches into a framework that can optimize any combination of
separable objectives and constraints. Experiments on five application domains
show the general applicability of this framework, while outperforming the
scalability of general-purpose solvers by a large margin.
