Alston, Validi, & Hicks

MILO formulations for binary classification trees

Mixed Integer Linear Optimization Formulations for
Learning Optimal Binary Classification Trees Brandon Alston, Hamidreza Validi,
Illya V. Hicks Computational Applied Mathematics and Operations Research, Rice
University, Houston, TX 77005, USA,
{bca3, hamidreza.validi<EMAIL_ADDRESS>
Decision trees are powerful tools for classification and regression that
attract many researchers working in the burgeoning area of machine learning.
One advantage of decision trees over other methods is their interpretability,
which is often preferred over other higher-accuracy methods that are
relatively uninterpretable. A binary classification tree has two types of
vertices: (i) branching vertices which have exactly two children and where
datapoints are assessed on a set of discrete features; and (ii) leaf vertices
at which datapoints are given a discrete prediction. An optimal binary
classification tree can be obtained by solving a biobjective optimization
problem that seeks to (i) maximize the number of correctly classified
datapoints and (ii) minimize the number of branching vertices. In this paper,
we propose four mixed integer linear optimization ($\operatorname{MILO}$)
formulations for designing optimal binary classification trees: two flow-based
formulations and two cut-based formulations. We provide theoretical
comparisons between our proposed formulations and the strongest flow-based
$\operatorname{MILO}$ formulation of Aghaei et al. (2021). We conduct
experiments on 13 publicly available datasets to show the models’ ability to
scale and the strength of a biobjective approach using Pareto frontiers. Our
code and data are available on GitHub.

optimal classification tree, mixed integer linear optimization, max-flow min-
cut

##  1 Introduction

Decision trees have been employed as tools in various applications including
decision making in management science (Magee 1964) and solving integer
optimization problems in operations research (Land and Doig 1960) since the
1960s. With the emergence of machine learning around 1980, Breiman et al.
(1984) applied decision trees to classification and regression problems. Since
1980, many heuristic approaches have been proposed to find quality feasible
solutions for the binary classification decision tree problem. Although
Breiman et al. (1984) were aware their heuristic algorithm was “one-step
optimal and not overall optimal”, they did not address the optimal decision
tree problem due to the immature computer technology of the 1980s.

In this paper, we focus on binary classification decision trees: trees in
which each parent has exactly two children. Due to their interpretability,
binary decision trees are used in a wide range of applications, including but
not limited to healthcare (Yoo et al. 2020, Li et al. 2021, Albaqami et al.
2021), geological surveying (Balk and Elder 2000), cyber-security (Maturana et
al. 2011, Kumar et al. 2013), financial analysis (Delen et al. 2013, Charlot
and Marimoutou 2014, Manogna and Mishra 2021), and more recently fair decision
making (Zhang and Ntoutsi 2019, Barata and Veenman 2021, Valdivia et al.
2021). Nearly all such applications use decision tree algorithms to select
features used for classification of future points, resulting in a supervised
machine learning method. Their interpretability is due to their lack of a
_black box_ nature and easy to understand branching rules and structure. This
interpretability is often preferred over higher-accuracy methods that are
relatively uninterpretable.

Optimal binary classification decision trees select binary tests to perform at
each branching vertex and classes to assign to each leaf vertex to maximize
prediction accuracy or minimize misclassification rate. However, Hyafil and
Rivest (1976) show building an optimal decision tree is NP-hard. Bessiere et
al. (2009) note greedy methods that build large trees perform inferior to
methods that find the smallest decision tree. Heuristics were first proposed
to find approximations of decision trees as computer technology was not
advanced enough to efficiently solve exact algorithms of the 1980s. Heuristic
approaches are often suboptimal and suffer from a number of shortcomings that
lead to solutions which need to be augmented in a post-process for better out-
of-sample test performance. Comparisons of heuristic-based tree models provide
useful outlines on which methods to use given specific conditions for
selecting attributes, but Murthy (2004) concludes no one heuristic for
splitting is superior to the others. Recently, optimization solvers such as
Gurobi and CPLEX, have become substantially more powerful (speedup factor of
450 billion over a 20 year period) through advancements in hardware, effective
use of cutting plane theory, disjunctive programming for branching rules, and
improved heuristic methods, as detailed by Bixby (2012). The Gurobi 9.5 update
led to 3X faster solution time of non-convex mixed integer quadratically
constrained programs compared to the previous release! These advancements
simultaneously eliminate the practical barrier for implementing Mixed Integer
Linear Optimization ($\operatorname{MILO}$) formulations to solve NP-hard
problems and the prejudice relevant during the inception of exact algorithms
for the optimal decision tree problem, as noted by Bertsimas and Dunn (2017).
Those interested in optimal binary decision trees turned to
$\operatorname{MILO}$ techniques for a number of reasons.

$\operatorname{MILO}$ formulations provide flexibility when choosing the
objective function(s) and constraints associated with building a decision
tree. Further, a greedy method generally finds local optima rather than a
global optimum; minimized impurity metrics at local branching nodes rather
than global classification metrics. There generally is no need to post-process
solutions of $\operatorname{MILO}$ formulations. $\operatorname{MILO}$
formulations provide provably (near) optimal solutions. Heuristics provide
quality feasible solutions, but even the most advanced methods that employ
gradient descent, fixed point iteration, or other optimization techniques may
require known optimal solutions and analytical gradients. Many real world
problems do not have these practically available, limiting the optimization
process, as noted by van der Blom et al. (2020). Continuous optimization
methods are difficult to apply as many real world problems have unique
constraints or need fair and robust solutions. Distribution based techniques
often yield solutions where perturbations on the training set are not
identical in the test set. Breiman et al. (1984) acknowledged their
classification and regression trees (CART) method induces biases in variables.
Kim and Loh (2001) showed CART presents bias toward selecting split variables
with more missing values and bias toward selecting surrogate variables with
fewer missing values due to the Gini being a function of the class proportions
and not the class sample sizes.

While some argue bias can be overcome by accumulating more data (Pereira et
al. 2009), the process is often challenging. Further, in decision trees one
interpretation related goal is understanding the relationships of features
selected. Given that greedy methods find branching splits independently, this
goal is not accomplished. $\operatorname{MILO}$ formulations find globally
optimal splits and yield solutions more aligned to such an interpretation
goal. Greedy methods, even with post-processing techniques, have difficulty
producing sparse and robust trees. This is much easier to do with constraints
of $\operatorname{MILO}$ formulations. Augmented traditional machine learning
techniques using multilayer perceptrons (MLPs), support vector machines
(SVMs), and recurrent or convolutional neural nets still yield black-box
models that require fine tuning of many parameters (Leung et al. 2003).
Further, there is debate on which optimization technique should be used to
solve such black-box models due to stability and other factors (Buciu et al.
2006, Ruiz et al. 2021).

We mention these characteristics of heuristic and traditional machine learning
formulations for decision trees to highlight the main differences between them
and those of $\operatorname{MILO}$ approaches. The plethora of methods makes
it challenging to pick the one most appropriate for a given dataset. In
practice heuristic formulations are still heavily used due to their speed and
often times known tuning parameters (Haber and Ruthotto 2017). Strong
$\operatorname{MILO}$ formulations are challenging to find due to the trade-
off between the number of decision variables needed and the size and structure
of the polyhedrons formed by their linear optimization (LO) relaxations
(Vielma 2015, Huchette and Vielma 2019). Modeling non-linear constraints has
gained increased interest in the literature (Bertsimas et al. 2021, Zhen et
al. 2022) while still hard to apply in practice. Most objective functions must
be convex for solvers to find global optima, but solver and polyhedral theory
advancements are eliminating this barrier (Steffy and Wolter 2013, Boland et
al. 2015, Perini et al. 2020, Witzig and Gleixner 2021). $\operatorname{MILO}$
formulation also tend to suffer scaling issues due to the large number of
decision variables required for a supervised learning algorithm.

In this paper, we propose four $\operatorname{MILO}$ formulations for finding
optimal binary decision trees and show their strong linear optimization (LO)
relaxations compared to current $\operatorname{MILO}$ formulations in the
literature. Through experimental testing on 13 publicly available datasets, we
highlight the practical application of the proposed $\operatorname{MILO}$
formulations and their ability to scale. In Section 2, we review related work
on binary decision trees. In Section 3, we propose our four
$\operatorname{MILO}$ formulations: two multi-commodity flow formulations
($\operatorname{MCF1}$ and $\operatorname{MCF2}$), and two cut-based
formulations ($\operatorname{CUT1}$ and $\operatorname{CUT2}$) for finding
optimal binary trees. In Section 4, we provide theoretical comparisons against
the most recent and strongest $\operatorname{MILO}$ formulation,
$\operatorname{FlowOCT}$, proposed by Aghaei et al. (2021). In Section 5, we
provide computational experiments supporting our theoretical results. Our goal
is to provide those interested in finding optimal binary decision trees a set
of implementable and flexible $\operatorname{MILO}$ formulations.

##  2 Related Work on Binary Decision Trees

Multiple heuristic approaches have been proposed to find quality feasible
solutions for the binary classification decision tree problem; e.g., CART
(Breiman et al. 1984), QUEST (Loh and Shih 1997), C4.5 (Quinlan 1993), SPRINT
(Shafer et al. 1996), SLIQ (Mehta et al. 1996), and CHAID (Kass 1980). These
heuristic methods use different metrics such as Shannon’s entropy (Shannon
1948) (generally referred to as entropy), the Gini index (Gini 1912),
information gain (Kullback and Leibler 1951) (referred to as the
Kullback–Leibler divergence in decision trees) and the Gain ratio (Quinlan
1986), all of which use a probability distribution function $P(X)$ for each
discrete random variable, $X=\\{x_{1},...,x_{n}\\}$ with probability of
observing each $x_{i}\in X$ as $P(x_{i})$. Many of the aforementioned methods
take _top-down_ approaches for building decision trees. Starting at the root
vertex, splits are determined by solving what can be defined as an
optimization problem. In the case of CART, ID3, and C4.5, a split is
determined by the minimum Gini index. Using this approach is greedy and each
split is determined independent of the others, leading to a tree that may not
adequately capture intrinsic relationships of the trained dataset; the tree
may also perform poorly on tested datasets due to over-fitting. A _top-down_
approach also requires pruning to not eliminate powerful splits “hidden”
behind weaker ones. These methods also have stopping criteria (complexity
penalties) to grow the tree as deep as possible before pruning, resulting in a
two stage learning approach. Lookahead heuristics such as IDX (Norton 1989),
LSID3 and ID3-k (Esmeir and Markovitch 2007) are used to simplify this
process, but Murthy et al. (1994) conclude it is unclear whether such methods
can lead to trees with better generalization ability.

In attempt to build more efficient trees, formulations with oblique splits are
also considered. Murthy et al. (1994) extend the work of Breiman et al. (1984)
by using hill-climbing techniques paired with randomization. Orsenigo and
Vercellis (2003) use discrete SVM operators counting misclassified points
rather than measuring distance at each node of the tree; sequential LP-based
heuristics are then employed to find the complete tree. Menze et al. (2011)
extend the oblique random forests first proposed by Breiman et al. (1984) with
linear discriminate analysis (LDA) to find optimal internal splits. Wang et
al. (2015) use logistic regression to find separating hyperplanes at branching
vertices while maintaining sparsity through a weight vector. Wickramarachchi
et al. (2016) employ Householder transformations to find oblique trees.

More recently augmented machine learning techniques have been employed to
build decision trees. Kontschieder et al. (2015) combine convolutional neural
nets and stochastic, differentiable decision trees to find global parameters
for branching and leaf vertices. Balestriero (2017) uses a modified hashing
neural net framework with sigmoid activation functions and independent
multilayer percepetrons that are equivalent to vertices of a decision tree;
this structure allows for oblique functions on each branching vertex and
imposes a global optimization problem that is differentiable with respect to
tuning parameters. Yang et al. (2018) use a one-layer neural network with a
softmax activation function and a _soft_ binning function for branching. Zhu
et al. (2020) use a 1-norm SVM to train decision trees. Zantedeschi et al.
(2020) propose using stochastic descent to generate branching attributes by
defining some pruning preference parameter $\eta\in\mathbb{R}$ and auxiliary
variables for linearity. Then a unique tree-structured isotonic optimization
algorithm is used to build a pruning-aware $\operatorname{MILO}$ formulation
for decision trees. Lee and Jaakkola (2020) note greedy oblique splitting
methods generally find poor local optima and show decision trees are related
to piece-wise linear neural nets with locally constant gradients.

Many of the methods mentioned above are counterintuitive as objective
functions are related to impurity measures on branching vertices rather than
datapoint misclassification metrics. Breiman et al. (1984) note continued
growth of the tree is indicative of successful splits and the growth itself is
a one-step optimization problem; thus, using unnatural objective functions
related to branching was acceptable. The more natural, and computationally
expensive, method is to build the tree in one problem. The unaligned objective
and the lack of computer technology made it infeasible to search all possible
partitions for such a method. Bertsimas and Dunn (2017) attribute failure to
produce optimal decision trees with heuristic methods because such methods do
not address the underlying problem of building a decision tree. Steps of
building a decision tree involve discrete decisions (which vertex to split on?
which variable to split with?) and discrete outcomes (is a datapoint correctly
classified? which leaf does a datapoint end on?). Therefore, one should
consider building optimal decision trees using $\operatorname{MILO}$
formulations.

To the best of our knowledge, Bennett and Blue (1996) propose the first
$\operatorname{MILO}$ formulation for designing optimal multivariate decision
trees. They fix (i) the structure of the tree, (ii) the number of branching
vertices and (iii) the classes of leaf vertices before solving the optimal
decision tree problem. They showed that optimal solutions of their problem lie
on the extreme points of the feasible set, even with a nonconvex objective
function. Further, they establish branching decisions as sets of disjunctive
linear constraints (Bennett 1995, Bennett and Mangasarian 1993).

Through considerable developments in integer optimization techniques and
employing them in commercial solvers, Bertsimas and Shioda (2007) introduced
CRIO (classification and regression via integer optimization) as a software
package that employs CPLEX 8.0 for solving optimization models. Bertsimas and
Dunn (2017) propose OCT (optimal classification trees) which outperforms CART
in accuracy. Narodytska et al. (2018) present a scalable SAT-based approach to
build an optimal tree of depth $D$. They generate valid binary encodings for a
specified number of vertices $N\leq D$, such that valid binary trees of size
$N$ can be generated; they also provide upper bounds on $N$. Verwer and Zhang
(2019) propose BinOCT, a binary-linear programming model aiming to reduce the
dependence of the problem size on the size of the training dataset. Dash et
al. (2018) and Firat et al. (2020) both propose column generation approaches.
Günlük et al. (2021) formulate IP models for decision trees with categorical
data. Optimal randomized classification trees (ORCT) from Blanquero et al.
(2021) uses a continuous optimization method for learning trees by replacing
discrete binary decisions in traditional trees with probabilistic decisions.

Researchers also use customized dynamic programming formulations to combat
searching over large spaces. DL8 of Nijssen and Fromont (2007) optimizes over
a ranking function to find an optimal decision tree under topology
constraints. DL8.5 of Aglin et al. (2020) improves upon DL8 through two
branch-and-bound approaches that cache itemsets used for cutting the search
space and only including vertices not in the cache in the branch-and-bound
cuts. The certifiable optimal rule lists (CORELS) method by Angelino et al.
(2017) creates optimal decision lists which can nontrivially be applied to a
tree structure through unique bit-vector libraries and specialized data
structures. The optimal sparse decision tree (OSDT) method of Hu et al. (2019)
extends CORELS and solves an exponentially harder decision tree problem,
yielding scaling issues. The MurTree method of Demirović et al. (2022)
introduces constraints on the depth and number of nodes to improve the
scalability of decision tree optimization with dynamic programming.

Recently, Aghaei et al. (2021) propose a $\operatorname{MILO}$ formulation
whose LP relaxation is at least as strong as that of OCT (Bertsimas and Dunn
2017) and BinOCT (Verwer and Zhang 2019). They modify the structure of a
traditional decision tree by adding a single source vertex and a single sink
vertex to turn the tree into a _directed acyclic graph_. Aghaei et al. (2021)
also propose two novel indices measuring disparate impact and disparate
treatment for learning fair decision trees. The main formulation of Aghaei et
al. (2021) is a flow-based $\operatorname{MILO}$ formulation where correctly
classified datapoints successfully _flow_ through the tree; a tailored
Benders’ decomposition is used for large size instances. Aghaei et al. (2021)
provide supporting theorems and proofs to show the strength of their
formulation against OCT (Bertsimas and Dunn 2017) and BinOCT (Verwer and Zhang
2019) and validity of their facet defining cuts used in their Benders’
decomposition.

##  3 MILO Formulations

In this section, we discuss a recent mixed integer linear optimization
($\operatorname{MILO}$) formulation proposed by Aghaei et al. (2021). Then, we
propose four $\operatorname{MILO}$ formulations (two flow-based and two cut-
based) for designing optimal binary classification trees. For brevity purposes
and ease of comparisons, we employ similar notations employed by Aghaei et al.
(2021). Given a training dataset $\mathcal{T}:=\\{x^{i},y^{i}\\}_{i\in I}$
consisting of datapoints indexed in the set $I$. Each row $i\in I$ of
$\mathcal{T}$ consists of binary features, indexed in the set $F$ and
collected in the vector $x^{i}\in\\{0,1\\}^{|F|}$, and a label $y^{i}$, drawn
from the finite set of $K$ classes. For every datapoint $i\in I$ and every
feature $f\in F$, binary parameter $x^{i}_{f}$ equals one if datapoint $i$
observes feature $f$. Graph $G_{h}=(V,E)$ denotes the input decision tree with
height $h$, where $1\leq h\in\mathbb{N}$ is the maximal depth of a
classification vertex in the assigned decision tree. The number of vertices
and edges of $G_{h}$ are represented by $n:=|V|=2^{h+1}-1$ and
$m:=|E|=2^{h+1}-2$, respectively. The vertex set $V$ is the union of the
branching vertex set, $B\subset V$, and the leaf vertex set, $L\subset V$,
with $B\cap L=\emptyset$.

An optimal binary classification tree can be obtained by solving a biobjective
optimization problem that seeks to (i) maximize the number of correctly
classified datapoints and (ii) minimize the number of branching vertices. For
every vertex $v\in V$, let $P_{1,v}$ and vertex set $V(P_{1,v})$ denote the
unique $1,v$-path from vertex 1 to vertex $v$ and the vertex set on the path
$P_{1,v}$ (including vertices $1$ and $v$), respectively. For every datapoint
$i\in I$ and every vertex $v\in V$, binary variable $s^{i}_{v}$ equals one if
datapoint $i$ is correctly classified at vertex $v$. For every vertex $v\in B$
and every feature $f\in F$, binary variable $b_{vf}$ equals one if vertex $v$
is branched on feature $f$. For every vertex $v\in V$ and every class $k\in
K$, binary variable $w_{vk}$ equals one if vertex $v$ is assigned to class
$k$. Finally for every vertex $v\in V$, binary variable $p_{v}$ equals one if
a prediction class is assigned to vertex $v$. Figure 1 illustrates directed
graph $D_{2}$ with assigned decision variables $b,w,$ and $p$.

$1$$b_{11}=1$$p_{1}=0$$2$$b_{23}=1$$p_{2}=0$$3$$w_{31}=1$$p_{3}=1$$4$$w_{42}=1$$p_{4}=1$$5$$w_{53}=1$$p_{5}=1$$6$$p_{6}=0$$7$$p_{7}=0$$B$$L$
Figure 1: Input decision tree $G_{2}=(B\cup L,E)$, branching vertex set
$B=\\{1,2,3\\}$ and leaf vertex set $L=\\{4,5,6,7\\}$. Here, vertices $1$ and
$2$ are branched on features 1 and 3, respectively; vertices $3$, $4$, and $5$
are assigned to a classes 1, 2, and 3, respectively; and vertices 6 and 7 are
pruned.

Employing binary decision variables for assigning binary tree structure is a
natural approach when considering the rules proposed by Bertsimas and Dunn
(2017). Many current methods ($\operatorname{MILO}$ or other) use a weighted
objective function to control tree sparsity and classification simultaneously.
We instead choose a bi-objective approach for a number of reasons. Without
proper normalization of the classification metric, the objective function may
be unfairly weighted when trying to find very sparse trees; tuning the weight
parameter may also be challenging. The Pareto frontiers generated by bi-
objective approaches provide efficient methods of analyzing tree sparsity on
classification metrics. The frontiers are easy to interpret visualizations to
compare tree out-of-sample performance with respect to sparsity and depth (or
model solution metrics with respect to tree topology). Since it is known
solutions of smaller trees are valid warm starts to solutions of larger trees,
the frontiers are generated efficiently.

A biobjective base model for designing optimal binary classification trees is
provided below.

$\displaystyle\max\leavevmode\nobreak\ \sum_{i\in I}\sum_{v\in V}s^{i}_{v}$
(1a) $\displaystyle\min\leavevmode\nobreak\ \sum_{v\in B}\sum_{f\in F}b_{vf}$
(1b) $\displaystyle p_{v}=\sum_{k\in K}w_{vk}$ $\displaystyle\forall v\in V$
(1c) $\displaystyle(\operatorname{BASE})\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ $ $\displaystyle\sum_{f\in
F}b_{vf}+\sum_{u\in V(P_{1,v})}p_{u}=1$ $\displaystyle\forall v\in V$ (1d)
$\displaystyle b_{vf}=0$ $\displaystyle\forall v\in L,\leavevmode\nobreak\
\forall f\in F$ (1e) $\displaystyle s^{i}_{v}\leq w_{vk}$
$\displaystyle\leavevmode\nobreak\ \forall i\in I:y^{i}=k,\leavevmode\nobreak\
\forall k\in K,\leavevmode\nobreak\ \forall v\in V$ (1f) $\displaystyle
b\in\\{0,1\\}^{n\times|F|},\leavevmode\nobreak\ w\in\\{0,1\\}^{n\times|K|},$
$\displaystyle p\in[0,1]^{n},\leavevmode\nobreak\ s\in\\{0,1\\}^{|I|\times
n}.$ (1g)

Here, objective function (1a) maximizes the number of correct classifications.
Objective function (1b) minimizes the number of branching vertices.
Constraints (1c) imply that a vertex is labeled with a prediction class if and
only if it is assigned to a class $k\in K$. Constraints (1d) imply that every
vertex $v\in V$ is either branched on a feature or a vertex on the $1,v$-path
is assigned to a prediction class. Constraints (1e) imply that no leaf vertex
is branched on a feature. Constraints (1f) imply that if datapoint $i\in I$ is
classified at vertex $v\in V$, then vertex $v$ is assigned to the class for
which $k=y^{i}$. Constraints (1g) specify the domain of all decision variables
of the base model. Furthermore, the polytope of the base model (1) is denoted
as follows,

$\displaystyle\mathscr{P}_{\operatorname{BASE}}\coloneqq\\{(b,w,p,s)\in[0,1]^{n(1+|I|+|F|+|K|)}:(b,w,p,s)\text{
satisfies constraints\leavevmode\nobreak\ \eqref{base1}-\eqref{base4}}\\}.$

###### Remark 3.1

Constraints $p\in[0,1]^{n}$, $w\in\\{0,1\\}^{n\times|K|}$, and (1c) imply that
$p\in\\{0,1\\}^{n}$.

Base model (1) ensures a valid binary decision tree structure. The base model
is pruning aware through constraints (1c) to prevent over-fitting in the final
decision tree; our models still produce balanced decision tree solutions.
Further, we can find optimal trees when an optimal depth is not known _a
priori_ by choosing $h$ to be large, increasing the search space and solution
time. The bi-objective approach also allows for objective (1b) to be used as a
constraint to control the sparsity of the final decision tree.

However, the base model (1) does not guarantee feasible connected paths for
datapoints to reach a correct classification vertex; that is, a datapoint can
“jump” onto classification vertex 5 without going through branching vertex 2
in Figure 1. Hence, we need complementary $\operatorname{MILO}$ formulations
with connectivity constraints to ensure that correctly classified datapoints
reach their corresponding classification vertex via feasible connected paths
through the tree. In the following sections, we discuss five connectivity
formulations: the flow-based connectivity formulation of Aghaei et al. (2021),
two new flow-based formulations ($\operatorname{MCF1}$ and
$\operatorname{MCF2}$), and two new cut-based formulations
($\operatorname{CUT1}$ and $\operatorname{CUT2}$). These formulations are
inspired by max-flow/min-cut formulations, as decision trees can be thought of
as directed acyclic networks.

###  3.1 Flow-based formulations

To impose a datapoint’s feasible path through the decision datapoint flow
variables are defined to find a connected $a,b$-flow through an augmented
tree. Currently $G_{h}$ can be thought of as a directed acyclic graph with a
single source, the root, and multiple sinks, leaf set $L$. Thus a datapoint
_flowing_ through the tree could end at more than one classification vertex.
To resolve this issue the tree must be augmented to have a single sink. It was
Aghaei et al. (2021) who first proposed such an augmentation of the decision
tree by appending a single source connected only to the root vertex and a
single sink connected to every vertex in the tree. Bertsimas and Dunn (2017)
and Hochbaum (2018) both propose network flow based models but do not augment
the tree. Network flow connectivity constraints are defined on this augmented
tree.

Consider augmentation of input decision tree $G_{h}$ into a tree with a single
source and sink as follows. Let $D_{h}=(V^{\prime},A)$ with
$V^{\prime}\coloneqq V\cup\\{t\\}$ and $A\coloneqq\\{(u,v)\mid\\{u,v\\}\in
E,\leavevmode\nobreak\ u<v\\}\cup\\{(v,t)\mid v\in V\\}$. Directed graph
$D_{h}$ adds a directed edge from $v\to t$ for all vertices of $V(G_{h})$,
thereby creating single sink vertex $t$. For every vertex $v\in V$, let (i)
$\ell(v)$ be the left child of vertex $v$; (ii) $r(v)$ be the right child of
vertex $v$; and (iii) $a(v)$ be the ancestor (parent) of vertex $v$ in
arborescence $G_{h}$. Note that for every $v\in L$, we have
$\ell(v)=r(v)=\emptyset$.

####  3.1.1 FlowOCT

Here we present the connectivity constraints of the imbalanced tree
formulation of Aghaei et al. (2021) with modifications for notation purposes.
For every datapoint $i\in I$ and every directed edge $(u,v)\in A$, variable
$z_{uv}^{i}$ denotes the flow of type $i$ on edge $(u,v)$. Since we have
$\ell(v)=r(v)=\emptyset$ for $v\in L$, for every datapoint $i\in I$ and every
vertex $v\in L$ we set variables $z_{v,\ell(v)}^{i}$ and $z_{v,r(v)}^{i}$ to
zero. Furthermore, we do not employ auxiliary vertex $s$ in the tree
structure. For every datapoint $i\in I$ and every vertex $v\in V$, we also
employ $s^{i}_{v}$ instead of flow variable $z_{vt}^{i}$ in formulation
$\operatorname{FlowOCT}$ to denote the terminal vertex of a datapoint. Figure
2 illustrates directed graph $D_{2}$ and the corresponding flow variables of
formulation $\operatorname{FlowOCT}$.

$\displaystyle(b,w,p,s)\in\mathscr{P}_{\operatorname{BASE}}$ (2a)
$\displaystyle z^{i}_{1,\ell(1)}+z^{i}_{1,r(1)}+s^{i}_{1}\leq 1$
$\displaystyle\forall i\in I$ (2b) $\displaystyle
z^{i}_{a(v),v}=z^{i}_{v,\ell(v)}+z^{i}_{v,r(v)}+s^{i}_{v}$
$\displaystyle\forall v\in V\setminus\\{1\\},\leavevmode\nobreak\ \forall i\in
I$ (2c) $\displaystyle(\operatorname{FlowOCT})\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ $ $\displaystyle
z^{i}_{v,\ell(v)}\leq\sum_{f\in F:x^{i}_{f}=0}b_{vf}$ $\displaystyle
z^{i}_{v,r(v)}\leq\sum_{f\in F:x^{i}_{f}=1}b_{vf}$ $\displaystyle\forall v\in
B,\leavevmode\nobreak\ \forall i\in I$ (2d) $\displaystyle
b\in\\{0,1\\}^{n\times|F|},\leavevmode\nobreak\ w\in\\{0,1\\}^{n\times|K|},$
$\displaystyle s\in\\{0,1\\}^{|I|\times n},\leavevmode\nobreak\
z\in\mathbb{R}^{|I|\times m}_{+}.$ (2e)

$s$$b_{11}$$p_{1}=0$$b_{23}$$p_{2}=0$$w_{31}$$p_{3}$$w_{42}$$p_{4}$$w_{51}$$p_{5}$$6$$p_{6}=0$$7$$p_{7}=0$$t$$z^{1}_{s1}$$z^{2}_{s1}$$z^{3}_{s1}$$z^{1}_{12}$$z^{2}_{12}$$z^{3}_{13}$$z^{1}_{24}$$z^{2}_{25}$$s^{3}_{3}$$s^{1}_{4}$$s^{2}_{5}$
Figure 2: Directed decision tree $D_{2}=(V^{\prime},A)$ with decision
variables of $\operatorname{FlowOCT}$. Source node $s$ is not used in our
formulation of $\operatorname{FlowOCT}$, but shown for understanding datapoint
flows. All decision variables shown equal one unless otherwise stated.

Here, constraints (2b) imply that for every datapoint $i\in I$ at most one
unit of flow of type $i$ can emanate from vertex 1. As we do not employ source
vertex $s$, these constraints are equivalent to one unit of flow for every
datapoint $i\in I$ emanates from source vertex $s$. Constraints (2c) imply
flow conservation for any datapoint $i\in I$ at any vertex $v\in
V\setminus\\{1\\}$. Constraints (2d) imply that if a flow of type $i\in I$ is
directed towards the left (right) child of a vertex, then the vertex is
branched on a feature $f\in F$ with $x^{i}_{f}=0$ ($x^{i}_{f}=1$).

$\operatorname{FlowOCT}$ augments a graph $G_{h}$ into input decision tree
$D_{h}$ by appending a directed edge from source node $s$ to the root vertex
and directed edges from every vertex $v\in V$ to sink vertex $t$; this creates
a directed acyclic graph. From there well establish network flow theory is
used to find connected feasible paths through the tree for a datapoint.
Branching is done through flow variables $z$. Successful classification of a
datapoint is defined by a connected $s,t$ path through the tree. Further, we
define the polytope of $\operatorname{FlowOCT}$ formulation as follows.

$\displaystyle\mathscr{P}_{\operatorname{FlowOCT}}\coloneqq\\{(b,w,p,s)\in\mathscr{P}_{\operatorname{BASE}},\leavevmode\nobreak\
z\in\mathbb{R}^{|I|\times m}_{+}:(b,w,p,s,z)\leavevmode\nobreak\
\text{satisfies constraints\leavevmode\nobreak\
\eqref{sina1}-\eqref{sina3}}\\}.$

###### Remark 3.2

The following constraints are implied in
$\mathscr{P}_{\operatorname{FlowOCT}}$.

$\displaystyle\sum_{v\in V}s^{i}_{v}\leq 1$ $\displaystyle\forall i\in I.$

###### Proof 3.3

Proof of Remark 3.2. For every datapoint $i\in I$, we have

$\displaystyle\sum_{v\in V}s^{i}_{v}$ $\displaystyle=\sum_{v\in V}s^{i}_{v}+0$
(3a) $\displaystyle=\sum_{v\in V}s^{i}_{v}+\Big{(}\sum_{v\in
V}\Big{(}z^{i}(\delta^{+}(v))+s^{i}_{v}-z^{i}(\delta^{-}(v))\Big{)}-\sum_{v\in
V}s^{i}_{v}\Big{)}$ (3b)
$\displaystyle=z^{i}(\delta^{+}(1))+s^{i}_{1}-z^{i}(\delta^{-}(1))+\sum_{v\in
V\setminus\\{1\\}}\Big{(}z^{i}(\delta^{+}(v))+s^{i}_{v}-z^{i}(\delta^{-}(v))\Big{)}$
(3c) $\displaystyle=z^{i}(\delta^{+}(1))+s^{i}_{1}-z^{i}(\delta^{-}(1))$ (3d)
$\displaystyle=z^{i}(\delta^{+}(1))+s^{i}_{1}$ (3e) $\displaystyle\leq 1.$
(3f)

Here, equality (3b) holds because the summation of all flows is zero in
directed graph $D_{h}$. Equality (3d) holds by constraints (2c). Equality (3e)
holds because the incoming flow to vertex one is zero in directed graph
$D_{h}$. Finally, inequality (3f) holds by constraints (2b).

####  3.1.2 MCF1

Here, we propose an extended version of formulation $\operatorname{FlowOCT}$
with same order in number of variables and constraints. We introduce a new
binary variable $q^{i}_{v}$ for every datapoint $i\in I$ and every vertex
$v\in V^{\prime}\coloneqq V\cup\\{t\\}$. Binary variable $q^{i}_{v}$ equals
one if datapoint $i$ enters vertex $v$ to reach terminal vertex $t\in
V^{\prime}$. Source node $s$ is consequently removed and classification is now
defined as a connected $1,t$ path through the tree as decision variables $q$
track a datapoint’s path. Figure 3 illustrates directed graph $D_{2}$ and the
corresponding flow variables of formulation $\operatorname{MCF1}$.

$\displaystyle(b,w,p,s)\in\mathscr{P}_{\operatorname{BASE}}$ (4a)
$\displaystyle z_{a(v),v}^{i}\leq q^{i}_{v}$ $\displaystyle\forall v\in
V\setminus\\{1\\},\leavevmode\nobreak\ \forall i\in I$ (4b) $\displaystyle
z_{a(v),v}^{i}=z_{v,\ell(v)}^{i}+z_{v,r(v)}^{i}+s^{i}_{v}$
$\displaystyle\forall v\in V\setminus\\{1\\},\leavevmode\nobreak\ \forall i\in
I$ (4c) $\displaystyle(\operatorname{MCF1})\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ $ $\displaystyle
z^{i}_{1,\ell(1)}+z^{i}_{1,r(1)}+s^{i}_{1}=q^{i}_{t}$ $\displaystyle\forall
i\in I$ (4d) $\displaystyle q^{i}_{\ell(v)}\leq\sum_{f\in
F:x^{i}_{f}=0}b_{vf}$ $\displaystyle q^{i}_{r(v)}\leq\sum_{f\in
F:x^{i}_{f}=1}b_{vf}$ $\displaystyle\forall v\in B,\leavevmode\nobreak\
\forall i\in I$ (4e) $\displaystyle
b\in\\{0,1\\}^{n\times|F|},\leavevmode\nobreak\ w\in\\{0,1\\}^{n\times|K|},$
$\displaystyle s\in\\{0,1\\}^{|I|\times n},\leavevmode\nobreak\
q\in\\{0,1\\}^{|I|\times|V^{\prime}|},\leavevmode\nobreak\
z\in\mathbb{R}^{|I|\times m}_{+}.$ (4f)

$b_{11}$$p_{1}=0$$b_{23}$$p_{2}=0$$q^{1}_{2}$$q^{2}_{2}$$w_{31}$$p_{3}$$q^{3}_{3}$$w_{42}$$p_{4}$$q^{1}_{4}$$w_{53}$$p_{5}$$q^{2}_{5}$$6$$p_{6}=0$$7$$p_{7}=0$$t$$z^{2}_{12}$$z^{1}_{12}$$z^{3}_{13}$$z^{1}_{24}$$z^{2}_{25}$$s^{3}_{3}$$s^{1}_{4}$$s^{2}_{5}$
Figure 3: Directed decision tree $D_{2}=(V^{\prime},A)$ with decision
variables of model $\operatorname{MCF1}$. All decision variables shown equal
one unless otherwise stated.

Here, constraints (4b) and (4c) imply that if vertex $v\in V^{\prime}$
receives a flow of type datapoint $i\in I$, then vertex $v$ is selected on a
$1,t$ path of datapoint $i$. Constraints (4c) imply flow conservation for each
data point $i\in I$ at vertex $v\in V\setminus\\{1\\}$. Constraints (4d) imply
that if datapoint $i\in I$ reaches vertex $t$, then either the datapoint is
correctly classified at vertex $1$ or a flow of type datapoint $i$ is
generated at vertex 1. Constraints (4e) imply that if the left (right) child
of parent $v\in V$ is selected on the path of datapoint $i\in I$, then
$x^{i}_{f}=0$ ($x^{i}_{f}=1$).

Now, we define the polytope of the $\operatorname{MCF1}$ model as follows.

$\displaystyle\mathscr{P}_{\operatorname{MCF1}}\coloneqq\Big{\\{}$
$\displaystyle(b,w,p,s)\in\mathscr{P}_{\operatorname{BASE}},\leavevmode\nobreak\
q\in[0,1]^{|I|\times|V^{\prime}|},\leavevmode\nobreak\
z\in\mathbb{R}^{|I|\times m}_{+}:$
$\displaystyle(b,w,p,s,q,z)\leavevmode\nobreak\ \text{satisfies
constraints\leavevmode\nobreak\ \eqref{mcf11}-\eqref{mcf14}}\Big{\\}}$

###### Remark 3.4

The following constraints are implied in $\mathscr{P}_{\operatorname{MCF1}}$.

$\displaystyle\sum_{v\in V}s^{i}_{v}=q^{i}_{t}$ $\displaystyle\forall i\in I.$

###### Proof 3.5

Proof of Remark 3.4. For every datapoint $i\in I$, we have

$\displaystyle\sum_{v\in V}s^{i}_{v}$ $\displaystyle=\sum_{v\in V}s^{i}_{v}+0$
(5a) $\displaystyle=\sum_{v\in V}s^{i}_{v}+\Big{(}\sum_{v\in
V}\Big{(}z^{i}(\delta^{+}(v))+s^{i}_{v}-z^{i}(\delta^{-}(v))\Big{)}-\sum_{v\in
V}s^{i}_{v}\Big{)}$ (5b)
$\displaystyle=z^{i}(\delta^{+}(1))+s^{i}_{1}-z^{i}(\delta^{-}(1))+\sum_{v\in
V\setminus\\{1\\}}\Big{(}z^{i}(\delta^{+}(v))+s^{i}_{v}-z^{i}(\delta^{-}(v))\Big{)}$
(5c) $\displaystyle=z^{i}(\delta^{+}(1))+s^{i}_{1}-z^{i}(\delta^{-}(1))$ (5d)
$\displaystyle=q^{i}_{t}.$ (5e)

Here, equality (5b) holds because the summation of net flow on all vertices is
zero. Equality (5d) holds by constraints (4c). Equality (5e) holds by
constraints (4d). This finishes the proof.

####  3.1.3 MCF2

This is a multi-commodity flow formulation in which flows are labeled by
datapoints and their destination. We define directed graph
$D^{\prime}_{h}\coloneqq D_{h}-t\coloneqq G_{h}$. For every datapoint $i\in
I$, every vertex $v\in V\setminus\\{1\\}$, and every directed edge $(c,d)\in
E\coloneqq E(G_{h})$, variable $z_{cd}^{iv}$ denotes the flow of type
datapoint $i$, emanating from the root and terminating at $v$ on directed edge
$(c,d)\in E$. Successful classification through the tree is now a connected
$1,v$-path. Figure 4 illustrates directed graph $D^{\prime}_{2}\coloneqq
G_{2}$ and the corresponding flow variables of formulation
$\operatorname{MCF2}$.

$\displaystyle(b,w,p,s)\in\mathscr{P}_{\operatorname{BASE}}$ (6a)
$\displaystyle z_{1,\ell(1)}^{iv}+z_{1,r(1)}^{iv}=s^{i}_{v}$
$\displaystyle\forall v\in V\setminus\\{1\\},\leavevmode\nobreak\ \forall i\in
I$ (6b) $\displaystyle z^{iv}_{u,\ell(u)}+z^{iv}_{u,r(u)}-z^{iv}_{a(u),u}=0$
$\displaystyle\forall u\in V\setminus\\{1,v\\},\leavevmode\nobreak\ \forall
v\in V\setminus\\{1\\},\leavevmode\nobreak\ \forall i\in I$ (6c)
$\displaystyle\sum_{u\in V\setminus\\{1\\}}z^{iu}_{a(v),v}\leq q^{i}_{v}$
$\displaystyle\forall v\in V\setminus\\{1\\},\leavevmode\nobreak\ \forall i\in
I$ (6d) $\displaystyle z^{iv}_{a(v),v}=s^{i}_{v}$ $\displaystyle\forall v\in
V\setminus\\{1\\},\leavevmode\nobreak\ \forall i\in I$ (6e)
$\displaystyle(\operatorname{MCF2})\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ $ $\displaystyle q^{i}_{\ell(v)}\leq\sum_{f\in
F:x^{i}_{f}=0}b_{vf}$ $\displaystyle q^{i}_{r(v)}\leq\sum_{f\in
F:x^{i}_{f}=1}b_{vf}$ $\displaystyle\forall v\in B,\leavevmode\nobreak\
\forall i\in I$ (6f) $\displaystyle\sum_{v\in V}s^{i}_{v}\leq 1$
$\displaystyle\forall i\in I$ (6g) $\displaystyle
b\in\\{0,1\\}^{n\times|F|},\leavevmode\nobreak\ w\in\\{0,1\\}^{n\times|K|},$
$\displaystyle s\in\\{0,1\\}^{|I|\times n},\leavevmode\nobreak\
q\in\\{0,1\\}^{|I|\times n},$ $\displaystyle z\in\mathbb{R}^{|I|\times n\times
m}_{+}.$ (6h)

$b_{11}$$p_{1}=0$$b_{23}$$p_{2}=0$$q^{1}_{2}$$q^{2}_{2}$$w_{31}$$p_{3}$$q^{3}_{3}$$s^{3}_{3}$$w_{42}$$p_{4}$$q^{1}_{4}$$s^{1}_{4}$$w_{53}$$p_{5}$$q^{2}_{5}$$s^{2}_{5}$$6$$p_{6}=0$$7$$p_{7}=0$$z^{25}_{12}$$z^{14}_{12}$$z^{33}_{13}$$z^{14}_{24}$$z^{25}_{25}$
Figure 4: Directed decision tree $D^{\prime}_{2}\coloneqq G_{2}$ with decision
variables of $\operatorname{MCF2}$. All decision variables shown equal one
unless otherwise stated.

Here, constraints (6b) imply that if datapoint $i\in I$ is correctly
classified at vertex $v\in V\setminus\\{1\\}$, then a flow of type $iv$
originates from vertex 1. Constraints (6c) imply the flow conservation of
datapoint $i$ heading towards vertex $v$ at vertex $u\in V\setminus\\{1,v\\}$.
Constraints (6d) imply that if a flow of datapoint $i\in I$ that is heading
toward vertex $u$ enters vertex $v$, then vertex $v$ is selected on the
$1,u$-path. Constraints (6e) imply that datapoint $i\in I$ is correctly
classified at vertex $v\in V\setminus\\{1\\}$ if and only if a flow of type
$iv$ enters vertex $v$. Constraints (6f) imply that if the left (right) child
of parent $v\in V$ is selected on the path of datapoint $i\in I$, then its
parent is branched on a feature $f\in F$ for which $x^{i}_{f}=0$
($x^{i}_{f}=1$). Constraints (6g) imply that each datapoint $i\in I$ can be
correctly classified in at most one vertex.

Now, we define the polytope of the $\operatorname{MCF2}$ model as follows.

$\displaystyle\mathscr{P}_{\operatorname{MCF2}}\coloneqq$
$\displaystyle\Big{\\{}(b,w,p,s)\in\mathscr{P}_{\operatorname{BASE}},\leavevmode\nobreak\
q\in[0,1]^{|I|\times|V^{\prime}|},\leavevmode\nobreak\
z\in\mathbb{R}^{|I|\times n\times m}_{+}:$
$\displaystyle(b,w,p,s,q,z)\leavevmode\nobreak\ \text{satisfies
constraints\leavevmode\nobreak\ \eqref{mcf21}-\eqref{mcf25}}\Big{\\}}$

###### Remark 3.6

The following constraints are implied in $\mathscr{P}_{\operatorname{MCF2}}$.

$\displaystyle z^{iv}_{a(v),v}-z^{iv}_{v,\ell(v)}-z^{iv}_{v,r(v)}=s^{i}_{v}$
$\displaystyle\forall v\in V\setminus\\{1\\},\leavevmode\nobreak\ \forall i\in
I,$ (7) $\displaystyle z^{iv}_{v,\ell(v)}+z^{iv}_{v,r(v)}=0$
$\displaystyle\forall v\in V\setminus\\{1\\},\leavevmode\nobreak\ \forall i\in
I.$ (8)

###### Proof 3.7

Proof of Remark 3.6. Let $(\hat{p},\hat{s},\hat{b},\hat{w},\hat{z},\hat{q})$
be a point that belongs to $\operatorname{MCF2}$. We are to show that the
point satisfies constraints (7). For every vertex $v\in V\setminus\\{1\\}$ and
every datapoint $i\in I$, we have

$\displaystyle\hat{z}^{iv}_{a(v),v}-\hat{z}^{iv}_{v,\ell(v)}-\hat{z}^{iv}_{v,r(v)}$
$\displaystyle=\hat{z}^{iv}(\delta^{-}(v))-\hat{z}^{iv}(\delta^{+}(v))-\sum_{u\in
V}\left(\hat{z}^{iv}(\delta^{-}(u))-\hat{z}^{iv}(\delta^{+}(u))\right)$ (9)
$\displaystyle=-\sum_{u\in
V\setminus\\{v\\}}\left(\hat{z}^{iv}(\delta^{-}(u))-\hat{z}^{iv}(\delta^{+}(u)\right)$
(10)
$\displaystyle=-\left(\hat{z}^{iv}(\delta^{-}(1))-\hat{z}^{iv}(\delta^{+}(1)\right)=\hat{z}_{1,\ell(1)}^{iv}+\hat{z}_{1,r(1)}^{iv}=\hat{s}^{i}_{v}.$
(11)

Here, equality (9) holds because the summation of the net flows on all
vertices of the graph is zero. Then, the last equality (11) holds by
constraints (6b).

Now we are to show that point
$(\hat{p},\hat{s},\hat{b},\hat{w},\hat{z},\hat{q})$ satisfies constraints (8).
For every vertex $v\in V\setminus\\{1\\}$ and every datapoint $i\in I$, we
have

$\displaystyle\hat{z}^{iv}_{v,\ell(v)}+\hat{z}^{iv}_{v,r(v)}=\hat{z}^{iv}_{a(v),v}-\hat{s}^{i}_{v}=\hat{s}^{i}_{v}-\hat{s}^{i}_{v}=0.$
(12)

Here, the first equality holds by implied equality (7). The second equality
holds by constraints (6e). This finishes the proof.

###  3.2 Cut-based formulations

In this section, we propose two cut-based formulations, both of which have
connectivity constraints that are added on-the-fly. Further, their
corresponding separation problems are solved in polynomial time; the
$1,v$-path of any vertex $v\in V(G_{h})$ is found in $\mathcal{O}(|V|)$
(Kaplan and Nussbaum 2011). The motivation behind our cut based formulation is
the $P_{1,v}$ of any vertex $v\in V$ is unique since $G_{h}$ is a tree. Thus
any vertex $c\in V(P_{1,v})$ is a valid $1,v$-separator. Through our
definition of variables $q$ and $s$ we can find $1,v$-separators for a
terminal vertex of a datapoint $i\in I$ to find a feasible path through the
tree.

####  3.2.1 CUT1

This formulation is the reduced formulation of $\operatorname{MCF2}$ as we
remove flow variables $z$. Here we aim to find $1,v$-separators strictly on
the $1,v$-path. For every vertex $v\in V$, we define $P_{v}$ as the set of
non-root vertices on the $1,v$-path.

$\displaystyle(b,w,p,s)\in\mathscr{P}_{\operatorname{BASE}}$ (13a)
$\displaystyle s^{i}_{v}\leq q^{i}_{c}$ $\displaystyle\forall c\in
V(P_{v}),\leavevmode\nobreak\ \forall v\in
V\setminus\\{1\\},\leavevmode\nobreak\ \forall i\in I$ (13b) $\displaystyle
q^{i}_{\ell(v)}\leq\sum_{f\in F:x^{i}_{f}=0}b_{vf}$
$\displaystyle(\operatorname{CUT1})\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ $ $\displaystyle q^{i}_{r(v)}\leq\sum_{f\in
F:x^{i}_{f}=1}b_{vf}$ $\displaystyle\forall v\in B,\leavevmode\nobreak\
\forall i\in I$ (13c) $\displaystyle\sum_{v\in V}s^{i}_{v}\leq 1$
$\displaystyle\forall i\in I$ (13d) $\displaystyle
b\in\\{0,1\\}^{n\times|F|},\leavevmode\nobreak\ w\in\\{0,1\\}^{n\times|K|},$
$\displaystyle s\in\\{0,1\\}^{|I|\times n},\leavevmode\nobreak\
q\in\\{0,1\\}^{|I|\times n}.$ (13e)

Here, constraints (13b) imply that if a datapoint $i\in I$ is classified at
vertex $v\in V\setminus\\{1\\}$, then all vertices on the path from $1$ to
$v$, excluding vertex 1, must be selected. Explanations of constraints (13c)
and (13d) are similar to those of constraints (6f) and (6g), respectively.

Further, we define the polytope of formulation (13) as follows.

$\displaystyle\mathscr{P}_{\operatorname{CUT1}}\coloneqq\Big{\\{}(b,w,p,s)\in\mathscr{P}_{\operatorname{BASE}},\leavevmode\nobreak\
q\in[0,1]^{|I|\times n}:(b,w,p,s,q)\leavevmode\nobreak\ \text{satisfies
constraints\leavevmode\nobreak\ \eqref{cut11}-\eqref{cut13}}\Big{\\}}.$

####  3.2.2 CUT2

We propose another cut-based formulation whose linear optimization relaxation
is stronger than that of formulation $\operatorname{CUT1}$ by redefining a
$1,v$-separator for a terminal vertex $v$. For every vertex $v\in
V\setminus\\{1\\}$, we define

$\displaystyle\operatorname{CHILD}(v)\coloneqq\\{u\in
V\setminus\\{v\\}:u>v,\leavevmode\nobreak\
\operatorname{dist}_{G_{h}}(v,u)<\infty\\},$

where $\operatorname{dist}_{G_{h}}(v,u)$ denotes the distance between vertices
$v$ and $u$ in directed graph $G_{h}$. For example in Figure 4,
$\operatorname{CHILD}(2)=\\{4,5\\}$. We redefine the set of $1,v$-separators
of a terminal vertex $v\in V$ as any vertex that separates $v$ or any one of
its children $(\\{v\\}\cup\operatorname{CHILD}(v))$. This holds as a datapoint
$i\in I$ must pass through $v$ to select $v$ or any one of its children as its
terminal vertex. Also, this provides stronger lower bounds on decision
variables $q$ when adding cuts at points in the branch and bound tree,
integral or fractional.

$\displaystyle(b,w,p,s)\in\mathscr{P}_{\operatorname{BASE}}$ (14a)
$\displaystyle s^{i}_{v}+\sum_{u\in\operatorname{CHILD}(v)}s^{i}_{u}\leq
q^{i}_{c}$ $\displaystyle\forall c\in V(P_{v}),\leavevmode\nobreak\ \forall
v\in V\setminus\\{1\\},\leavevmode\nobreak\ \forall i\in I$ (14b)
$\displaystyle q^{i}_{\ell(v)}\leq\sum_{f\in F:x^{i}_{f}=0}b_{vf}$
$\displaystyle(\operatorname{CUT2})\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ $ $\displaystyle q^{i}_{r(v)}\leq\sum_{f\in
F:x^{i}_{f}=1}b_{vf}$ $\displaystyle\forall v\in B,\leavevmode\nobreak\
\forall i\in I$ (14c) $\displaystyle\sum_{v\in V}s^{i}_{v}\leq 1$
$\displaystyle\forall i\in I$ (14d) $\displaystyle
b\in\\{0,1\\}^{n\times|F|},\leavevmode\nobreak\ w\in\\{0,1\\}^{n\times|K|},$
$\displaystyle s\in\\{0,1\\}^{|I|\times n},\leavevmode\nobreak\
q\in\\{0,1\\}^{|I|\times n}.$ (14e)

Here, constraints (14b) imply that if a datapoint $i\in I$ is correctly
classified at vertex $v$ or one of its descendants, then the datapoint passes
through every vertex on the path from $1$ to $v$ excluding vertex 1.
Interpretations of constraints (14c) and (14d) are similar to those of
constraints (6f) and (6g), respectively.

Further, we define the polytope of formulation (14) as follows.

$\displaystyle\mathscr{P}_{\operatorname{CUT2}}\coloneqq\Big{\\{}(b,w,p,s)\in\mathscr{P}_{\operatorname{BASE}},\leavevmode\nobreak\
q\in[0,1]^{|I|\times n}:(b,w,p,s,q)\leavevmode\nobreak\ \text{satisfies
constraints\leavevmode\nobreak\ \eqref{cut21}-\eqref{cut23}}\Big{\\}}.$

##  4 Theoretical comparison of formulations

In this section, we prove Theorem 4.1, comparing the strength of the
formulations discussed in Section 3. The theorem follows directly by Lemmata
4.3 through 4.9, which show formulations $\operatorname{CUT2}$ through
$\operatorname{MCF1}$ are just as strong as that of $\operatorname{FlowOCT}$.
Lemma 4.3 shows a strict inclusion between $\operatorname{CUT2}$ and
$\operatorname{CUT1}$ through an example. Lemma 4.5 show the equivalence of
formulations $\operatorname{MCF2}$ and $\operatorname{CUT1}$ due to max-flow
min-cut result of Ford and Fulkerson (1962). Lemma 4.7 shows
$\operatorname{MCF1}$ and $\operatorname{MCF2}$ are equivalent to each other
due to the unique $1,v$-paths of a decision tree. Lemma 4.9 shows the strong
LO relaxation of $\operatorname{MCF1}$ against $\operatorname{FlowOCT}$. Note
that our Theorem 4.1 and Theorem 1 of Aghaei et al. (2021) suffice to show our
formulations are at least as strong as that of recent $\operatorname{MILO}$
formulations OCT (Bertsimas and Shioda 2007) and BinOCT (Verwer and Zhang
2019). Lastly, we show the correctness of our proposed formulations through
Theorems 4.11 and 4.12.

######  Theorem 4.1 (Strength of Formulations)

Let $X=(b,w,p,s,q)$. Then,

$\displaystyle\mathscr{P}_{\operatorname{CUT2}}\subseteq\mathscr{P}_{\operatorname{CUT1}}=\operatorname{proj}_{X}\mathscr{P}_{\operatorname{MCF2}}=\operatorname{proj}_{X}\mathscr{P}_{\operatorname{MCF1}}\subseteq\operatorname{proj}_{X}\mathscr{P}_{\operatorname{FlowOCT}}.$

###### Proof 4.2

Proof of Theorem 4.1. The proof follows by Lemmata (4.3), (4.5), (4.7), and
(4.9).

Lemma 4.3 shows that the $\operatorname{CUT2}$ model is at least as strong as
the $\operatorname{CUT1}$ model.

###### Lemma 4.3

$\mathscr{P}_{\operatorname{CUT2}}\subseteq\mathscr{P}_{\operatorname{CUT1}}$,
and the inclusion can be strict.

###### Proof 4.4

Proof of Lemma 4.3. Let $(\hat{p},\hat{s},\hat{b},\hat{w},\hat{q})$ be a point
that belongs to $\operatorname{CUT2}$. We are to show that it also belongs to
$\operatorname{CUT1}$. It is clear that the point satisfies constraints (13a),
(13c), and (13d). For every datapoint $i\in I$ and for every vertex $v\in V$
and for every separating vertex $c\in P_{v}$, we show that point
$(\hat{p},\hat{s},\hat{b},\hat{w},\hat{q})$ satisfies constraints (13b).

$\displaystyle\hat{s}^{i}_{v}\leq\hat{s}^{i}_{v}+\sum_{u\in\operatorname{CHILD}(v)}\hat{s}^{i}_{u}\leq\hat{q}^{i}_{c}$

The first inequality holds by the nonnegatviity of $\hat{s}^{i}_{v}$ for all
$v\in V$ and $i\in I$. The second inequality holds by constraints (14b). This
completes the proof.

Furthermore, Figure 5 illustrates an instance of the optimal binary decision
tree problem that belongs to the $\mathscr{P}_{\operatorname{CUT1}}$ polytope,
but not the $\mathscr{P}_{\operatorname{CUT2}}$ polytope. In this instance, we
have one datapoint with three features and one class. Furthermore, we have all
features equal to zero, $x^{1}_{1}=x^{1}_{2}=x^{1}_{3}=0$, and class
$y^{1}=1$. The fractional point in the branch and bound tree indicates three
branching vertices 1, 2, and 4, (using features 1, 2, and 3, respectively) and
4 classification vertices 3, 5, 8 and 9 (all of which use class $k=1$);
vertices 6 and 7 are not shown for clarity purposes. Further, the datapoint
enters vertices 1, 2, 4, 8 and 9 and selects vertices 4, 8, and 9 as possible
terminal vertices. Note the datapoint does not select vertices 3 and 5. While
the fractional point belongs to the polytope
$\mathscr{P}_{\operatorname{CUT1}}$, it does not belong to
$\mathscr{P}_{\operatorname{CUT2}}$ because it violates constraints (14b) for
terminal vertex $v=4$ and its separating vertex $c=2$. In simpler terms,

$\displaystyle\bar{s}^{1}_{4}+\sum_{u\in\operatorname{CHILD}[4]}\bar{s}^{1}_{u}=\bar{s}_{4}^{1}+\bar{s}_{8}^{1}+\bar{s}_{9}^{1}=0.1+0.1+0=0.2\not\leq
0.15=q_{2}^{1}.$

This completes the proof.

Figure 5: A point that belongs to $\mathscr{P}_{\operatorname{CUT1}}$, but not
$\mathscr{P}_{\operatorname{CUT2}}$.$1$$\bar{b}_{11}=0.75,\leavevmode\nobreak\
\bar{q}_{1}^{1}=1$$\bar{p}_{1}=0.25,\leavevmode\nobreak\ \bar{w}_{11}=0.25$,
$\bar{s}^{1}_{1}=0$$2$$\bar{b}_{22}=0.25,\leavevmode\nobreak\
\bar{w}_{21}=0.5$$\bar{p}_{2}=0.5,\leavevmode\nobreak\
\bar{q}_{2}^{1}=0.15$$\bar{s}^{1}_{2}=0$$3$$\bar{b}_{31}=\bar{b}_{32}=\bar{b}_{33}=0$$\bar{p}_{3}=0.75,\leavevmode\nobreak\
\bar{w}_{31}=0.75$$\bar{q}_{3}^{1}=0,\leavevmode\nobreak\
\bar{s}^{1}_{3}=0$$4$$\bar{b}_{43}=0.1,\leavevmode\nobreak\
\bar{w}_{41}=0.15$$\bar{p}_{4}=0.15,\leavevmode\nobreak\
\bar{q}_{4}^{1}=0.1$$\bar{s}^{1}_{4}=0.1$$5$$\bar{b}_{51}=\bar{b}_{52}=\bar{b}_{53}=0$$\bar{p}_{5}=0.25,\leavevmode\nobreak\
\bar{w}_{51}=0.25$$\bar{q}_{5}^{1}=0,\leavevmode\nobreak\
\bar{s}^{1}_{5}=0$$8$$\bar{b}_{81}=\bar{b}_{82}=\bar{b}_{83}=0$$\bar{p}_{8}=0.1,\leavevmode\nobreak\
\bar{w}_{81}=0.1$$\bar{q}_{8}^{1}=0.1,\leavevmode\nobreak\
\bar{s}^{1}_{8}=0.1$$9$$\bar{b}_{91}=\bar{b}_{92}=\bar{b}_{93}=0$$\bar{p}_{9}=0.1,\leavevmode\nobreak\
\bar{w}_{91}=0.1$$\bar{q}_{9}^{1}=0,\leavevmode\nobreak\ \bar{s}^{1}_{9}=0$

Lemma 4.5 shows that $\operatorname{MCF2}$ is an extended formulation for
$\operatorname{CUT1}$.

###### Lemma 4.5

Let $X=(b,w,p,s,q)$. Then,
$\mathscr{P}_{\operatorname{CUT1}}=\operatorname{proj}_{X}\mathscr{P}_{\operatorname{MCF2}}$.

###### Proof 4.6

Proof of Lemma 4.5. ($\supseteq$) Let
$(\hat{p},\hat{s},\hat{b},\hat{w},\hat{q},\hat{z})$ be a point that belongs to
polytope $\mathscr{P}_{\operatorname{MCF2}}$. We are to show that point
$(\hat{p},\hat{s},\hat{b},\hat{w},\hat{q})$ belongs to polytope
$\mathscr{P}_{\operatorname{CUT1}}$. It suffices to show that
$(\hat{p},\hat{s},\hat{b},\hat{w},\hat{q})$ satisfies constraints (13b). For
every datapoint $i\in I$, every vertex $v\in V\setminus\\{1\\}$, and every cut
vertex $c$ on the path $P_{v}$, let $R$ be the set of reachable vertices from
vertex 1 in tree $G-c$. Then, we have

$\displaystyle\hat{s}^{i}_{v}$
$\displaystyle=\hat{z}^{iv}_{1,\ell(1)}+\hat{z}^{iv}_{1,r(1)}$ (15a)
$\displaystyle=\hat{z}^{iv}_{1,\ell(1)}+\hat{z}^{iv}_{1,r(1)}+\hat{z}^{iv}(\delta^{+}(R\setminus\\{1\\}))-\hat{z}^{iv}(\delta^{-}(R\setminus\\{1\\}))$
(15b) $\displaystyle\leq\hat{z}^{iv}(\delta^{+}(R))-0$ (15c)
$\displaystyle=\hat{z}^{iv}(\delta^{-}(c))$ (15d) $\displaystyle\leq\sum_{u\in
V\setminus\\{1\\}}\hat{z}^{iu}(\delta^{-}(c))$ (15e)
$\displaystyle\leq\hat{q}^{i}_{c}.$ (15f)

Here, equality (15a) holds by constraints (6b). Equality (15b) holds by flow
conservation constraints (6c). Inequality (15c) holds by nonnegativity of $z$
variables. Equality (15d) holds because vertex $c$ is a $1,v$-separator.
Inequality (15e) holds by nonnegativity of $z$ variables. Finally, inequality
(15f) holds by constraints (6d).

($\subseteq$) Let $(\hat{b},\hat{w},\hat{s},\hat{p},\hat{q})$ be a point that
belongs to $\mathscr{P}_{\operatorname{CUT1}}$. We are to show that there
exists $\bar{z}$ such that $(\hat{b},\hat{w},\hat{s},\hat{p},\hat{q},\bar{z})$
belongs to $\mathscr{P}_{\operatorname{MCF1}}$. It suffices to show that the
point satisfies constraints (6b)-(6d). To construct $\bar{z}$, we solve the
following max-flow problem for every datapoint $i\in I$ and every vertex $v\in
V\setminus\\{1\\}$.

$\displaystyle\max\leavevmode\nobreak\ $ $\displaystyle
z^{iv}(\delta^{+}(1))-z^{iv}(\delta^{-}(1))$ (16a) s.t. $\displaystyle
z^{iv}(\delta^{+}(u))-z^{iv}(\delta^{-}(u))=0$ $\displaystyle\forall u\in
V\setminus\\{1,v\\},\leavevmode\nobreak\ \forall i\in I$ (16b) $\displaystyle
z^{iv}(\delta^{-}(v))\leq\hat{s}_{v}^{i}$ (16c) $\displaystyle
z^{iv}(\delta^{-}(u))\leq\frac{\hat{q}^{i}_{v}}{n-2}$ $\displaystyle\forall
u\in V\setminus\\{1,v\\},\leavevmode\nobreak\ \forall i\in I$ (16d)
$\displaystyle z^{iv}_{a}\geq 0$ $\displaystyle\forall v\in
V,\leavevmode\nobreak\ \forall i\in I,\leavevmode\nobreak\ \forall a\in E(G).$
(16e)

Let $\bar{z}$ be an optimal solution obtained by solving the max-flow problem
(16) for every datapoint $i\in I$ and every vertex $u\in V\setminus\\{1\\}$.
It is clear that point $(\hat{b},\hat{w},\hat{s},\hat{p},\hat{q},\bar{z})$
satisfies constraints (6c) because it satisfies constraints (16b).
Furthermore, one can sum up both sides of constraints (16d) on vertices
$V\setminus\\{1,v\\}$. This results in

$\displaystyle\sum_{u\in
V\setminus\\{1,v\\}}\bar{z}^{iv}(\delta^{-}(u))\leq\sum_{u\in
V\setminus\\{1,v\\}}\frac{\hat{q}^{i}_{v}}{n-2}=\hat{q}^{i}_{v}.$ (17)

Hence, constraints (6d) are satisfied. Now we show that
$(\hat{b},\hat{w},\hat{s},\hat{p},\hat{q},\bar{z})$ satisfies constraints
(6b). For every datapoint $i\in I$, every vertex $v\in V\setminus\\{1\\}$ and
every $1,v$-separator $c\in P_{v}$, we have

$\displaystyle\hat{s}^{i}_{v}\leq\hat{q}^{i}_{c}=\bar{z}^{iv}(\delta^{+}(1))-\bar{z}^{iv}(\delta^{-}(1))\leq\hat{s}^{i}_{v}.$

Here, the first inequality holds by constraints (13b) The first equality holds
by the max-flow/min-cut result of Ford and Fulkerson (1962). The last
inequality holds because

$\displaystyle\bar{z}^{iv}(\delta^{+}(1))-\bar{z}^{iv}(\delta^{-}(1))$
$\displaystyle=\bar{z}^{iv}(\delta^{+}(1))-\bar{z}^{iv}(\delta^{-}(1))-\sum_{u\in
V}\left(\bar{z}^{iv}(\delta^{+}(u))-\bar{z}^{iv}(\delta^{-}(u))\right)$
$\displaystyle=-\sum_{u\in
V\setminus\\{1\\}}\left(\bar{z}^{iv}(\delta^{+}(u))-\bar{z}^{iv}(\delta^{-}(u))\right)$
$\displaystyle=-\left(\bar{z}^{iv}(\delta^{+}(v))-\bar{z}^{iv}(\delta^{-}(v))\right)$
$\displaystyle=\bar{z}^{iv}(\delta^{-}(v))-\bar{z}^{iv}(\delta^{+}(v))\leq\bar{z}^{iv}(\delta^{-}(v))\leq\hat{s}^{i}_{v}.$

Here, the first equality holds because $\sum_{u\in
V}\left(\bar{z}^{iv}(\delta^{+}(u))-\bar{z}^{iv}(\delta^{-}(u))\right)=0$ for
every datapoint $i\in I$ and every vertex $v\in V\setminus\\{1\\}$. The third
equality holds by constraints (16b). The last inequality holds by constraints
(16c). This concludes the proof.

###### Lemma 4.7

Let $X=(b,w,p,s,q)$. Then
$\operatorname{proj}_{X}\mathscr{P}_{\operatorname{MCF2}}=\operatorname{proj}_{X}\mathscr{P}_{\operatorname{MCF1}}$.

###### Proof 4.8

Proof of Lemma 4.7. ($\subseteq$) Let
$(\hat{p},\hat{s},\hat{b},\hat{w},\hat{q},\hat{z})$ be a point that belongs to
$\mathscr{P}_{\operatorname{MCF2}}$. We are to show that there exist $\bar{z}$
and $\bar{q}$ such that
$(\hat{p},\hat{s},\hat{b},\hat{w},\bar{q},\bar{z})\in\mathscr{P}_{\operatorname{MCF1}}$.
For every datapoint $i\in I$ and directed edge $(u,v)\in E(D_{h}^{\prime})$,
we define

$\displaystyle\bar{z}_{uv}^{i}:=\sum_{p\in
V\setminus\\{1\\}}\hat{z}^{ip}_{uv}.$ (18)

For every datapoint $i\in I$ and every vertex $v\in V$, we define
$\bar{q}^{i}_{v}:=\hat{q}^{i}_{v}$. For every datapoint $i\in I$ and vertex
$t\in V^{\prime}$, we define

$\displaystyle\bar{q}^{i}_{t}:=\sum_{v\in V}\hat{s}^{i}_{v}.$ (19)

We note that $\bar{q}^{i}_{t}\leq 1$ by constraints (6g). Further, it is clear
that
$(\hat{p},\hat{s},\hat{b},\hat{w},\bar{z},\bar{q})\in\mathscr{P}_{\operatorname{BASE}}$.
So, it suffices to show that
$(\hat{p},\hat{s},\hat{b},\hat{w},\bar{z},\bar{q})$ satisfies constraints
(4b)-(4e). For every datapoint $i\in I$ and every vertex $v\in
V\setminus\\{1\\}$, we show that
$(\hat{p},\hat{s},\hat{b},\hat{w},\bar{z},\bar{q})$ satisfies constraints
(4b).

$\displaystyle\bar{z}^{i}_{a(v),v}$ $\displaystyle=\sum_{u\in
V\setminus\\{1\\}}\hat{z}^{iu}_{a(v),v}\leq\hat{q}^{i}_{v}=\bar{q}^{i}_{v}.$

Here, the first equality holds by definition (18). The first inequality holds
by constraints (6d). The last equality holds by the definition of $\bar{q}$.

For every datapoint $i\in I$ and for every vertex $v\in V\setminus\\{1\\}$, we
are to show that $(\hat{p},\hat{s},\hat{b},\hat{w},\bar{z},\bar{q})$ satisfies
constraints (4c).

$\displaystyle\bar{z}^{i}_{a(v),v}-\bar{z}^{i}_{v,\ell(v)}-\bar{z}^{i}_{v,r(v)}$
$\displaystyle=\sum_{u\in V\setminus\\{1\\}}\hat{z}^{iu}_{a(v),v}-\sum_{u\in
V\setminus\\{1\\}}(\hat{z}^{iu}_{v,\ell(v)}+\hat{z}^{iu}_{v,r(v)})$
$\displaystyle=\sum_{u\in V\setminus\\{1,v\\}}\hat{z}^{iu}_{a(v),v}-\sum_{u\in
V\setminus\\{1,v\\}}(\hat{z}^{iu}_{v,\ell(v)}+\hat{z}^{iu}_{v,r(v)})$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
+\hat{z}^{iv}_{a(v),v}-(\hat{z}^{iv}_{v,\ell(v)}+\hat{z}^{iv}_{v,r(v)})$
$\displaystyle=0+\hat{z}^{iv}_{a(v),v}-(\hat{z}^{iv}_{v,\ell(v)}+\hat{z}^{iv}_{v,r(v)})$
$\displaystyle=0+\hat{s}^{i}_{v}-0=\hat{s}^{i}_{v}.$

Here, the first equality holds by definition (18). The third equality holds by
constraints (6c). Finally, the last line holds by constraints (6e) and implied
constraints (8).

For every datapoint $i\in I$, we show that point
$(\hat{p},\hat{s},\hat{b},\hat{w},\bar{z},\bar{q})$ satisfies constraints
(4d).

$\displaystyle\bar{q}^{i}_{t}$ $\displaystyle=\sum_{v\in V}\hat{s}^{i}_{v}$
$\displaystyle=\hat{s}^{i}_{1}+\sum_{v\in V\setminus\\{1\\}}\hat{s}^{i}_{v}$
$\displaystyle=\hat{s}^{i}_{1}+\sum_{v\in
V\setminus\\{1\\}}\left(\hat{z}^{iv}_{1,\ell(1)}+\hat{z}^{iv}_{1,r(1)}\right)$
$\displaystyle=\hat{s}^{i}_{1}+\bar{z}^{i}_{1,\ell(1)}+\bar{z}^{i}_{1,r(1)}.$

Here, the first equality holds by definition (19). The third equality holds by
constraints (6b). Finally, the last equality holds by definition (18).
Further, it is clear that $(\hat{p},\hat{s},\hat{b},\hat{w},\bar{z},\bar{q})$
satisfies constraints (4e) by the definition of $\bar{q}^{i}_{v}$ for every
datapoint $i\in I$ and vertex $v\in V$; i.e.,
$\bar{q}^{i}_{v}:=\hat{q}^{i}_{v}$.

($\supseteq$) As
$\mathscr{P}_{\operatorname{CUT1}}=\operatorname{proj}_{X}\mathscr{P}_{\operatorname{MCF2}}$
by Lemma 4.5, it suffices to show that
$\mathscr{P}_{\operatorname{CUT1}}\supseteq\operatorname{proj}_{X}\mathscr{P}_{\operatorname{MCF1}}$.
Let $(\hat{p},\hat{s},\hat{b},\hat{w},\hat{q},\hat{z})$ be a point that
belongs to $\mathscr{P}_{\operatorname{MCF1}}$. We are to show that
$(\hat{p},\hat{s},\hat{b},\hat{w},\hat{q})$ belongs to the
$\mathscr{P}_{\operatorname{CUT1}}$ polytope. It suffices to show that
$(\hat{p},\hat{s},\hat{b},\hat{w},\hat{q})$ satisfies constraints (13b) and
(13d). For every datapoint $i\in I$, for every vertex $v\in
V\setminus\\{1\\}$, for every cut vertex $c\in V(P_{v})$, we have,

$\displaystyle\hat{s}^{i}_{v}\leq\hat{z}^{i}(\delta^{-}(v))\leq\hat{z}^{i}(\delta^{-}(c))\leq\hat{q}^{i}_{c}.$

Here, the first and second inequalities hold by flow conservation constraints
(4c). The last inequality holds by constraints (4b).

Now we show that the point satisfies constraints (13d).

$\displaystyle\sum_{v\in V}\hat{s}^{i}_{v}=\hat{q}^{i}_{t}\leq 1.$

Here, the equality holds by the implied constraints of Remark 3.6. The
inequality holds because $\hat{q}^{i}_{t}$ is a binary variable. This
completes the proof.

###### Lemma 4.9

Let $X=(b,w,p,s,q)$. Then
$\operatorname{proj}_{X}\mathscr{P}_{\operatorname{MCF1}}\subseteq\operatorname{proj}_{X}\mathscr{P}_{\operatorname{FlowOCT}}$.

###### Proof 4.10

Proof of Lemma 4.9. Let $(\hat{p},\hat{s},\hat{b},\hat{w},\hat{q},\hat{z})$ be
a point that belongs to the $\mathscr{P}_{\operatorname{MCF1}}$ polytope. We
are to show that the point belongs to the polytope
$\mathscr{P}_{\operatorname{FlowOCT}}$. First, it is clear that
$(\hat{p},\hat{s},\hat{b},\hat{w},\hat{q},\hat{z})\in\mathscr{P}_{\operatorname{BASE}}$;
so, it satisfies constraint (2a).

It suffices to show that $(\hat{p},\hat{s},\hat{b},\hat{w},\hat{q},\hat{z})$
satisfies constraints (2b)-(2d). For every datapoint $i\in I$, we have

$\displaystyle\hat{z}^{i}_{1,\ell(1)}+\hat{z}^{i}_{1,r(1)}+\hat{s}^{i}_{1}=\hat{q}^{i}_{t}\leq
1.$

Here, the equality holds by constraints (4d). The inequality holds because
$\hat{q}\in[0,1]^{|I|\times|V^{\prime}|}$. Hence, point
$(\hat{p},\hat{s},\hat{b},\hat{w},\hat{q},\hat{z})$ satisfies constraints
(2b). Because $(\hat{p},\hat{s},\hat{b},\hat{w},\hat{z},\hat{q})$ satisfies
constraints (4c), the point satisfies constraints (2c). Finally for every
datapoint $i\in I$ and every vertex $v\in B$, we have

$\displaystyle\hat{z}^{i}_{v,\ell(v)}\leq\hat{q}^{i}_{\ell(v)}\leq\sum_{f\in
F:x^{i}_{f}=0}\hat{b}_{vf},$ (20a)
$\displaystyle\hat{z}^{i}_{v,r(v)}\leq\hat{q}^{i}_{r(v)}\leq\sum_{f\in
F:x^{i}_{f}=1}\hat{b}_{vf}.$ (20b)

Here, the first inequalities in (20a) and (20b) hold by constraints (4b). The
second inequalities in (20a) and (20b) hold by constraints (4e). Hence, point
$(\hat{p},\hat{s},\hat{b},\hat{w},\hat{z},\hat{q})$ satisfies constraints
(2d). This concludes the proof.

The following two theorems show the correctness of our proposed models.

###### Theorem 4.11

Let $p^{*}\in\mathscr{P}_{\operatorname{FlowOCT}}$ be a feasible solution of
formulation (2). Then $p^{*}$ represents a feasible binary classification
tree.

###### Theorem 4.12

Suppose that a point $p^{*}$ represents a feasible binary classification tree.
Then, $p^{*}\in\mathscr{P}_{\operatorname{CUT2}}$.

First, we will prove Theorem 4.11.

###### Proof 4.13

Proof of Theorem 4.11. Let $p^{*}\in\mathscr{P}_{\operatorname{FlowOCT}}$ be
defined by binary variables $b,w,p,s,q$. We are to show $p^{*}$ represents an
optimal binary classification tree. Variables $b,w,p$ are defined on a vertex
set $B\subseteq V$ and $L\subseteq V$ where $|V|=2^{h+1}-1$ and $h\geq 1$ is
integral and represents the maximal depth of a vertex in an unassigned binary
decision tree. Further $B\cap L=\emptyset$. On each vertex $v\in V$ the left
and right children are defined as $\ell(v),r(v)$ and the set of non-root
vertices on the unique $1,v$-path as $P_{1,v}$. Further decision variables $b$
and $w$ are defined on binary encoded feature set $F$ and discrete class set
$K$, respectively, of given training dataset $I$. Constraints (1c)-(1e) impose
a valid tree structure through the following. For each $p_{v}=1$, then
$\sum_{k\in K}w_{vk}=1$ by (1c). Thus exactly one $k\in K$ was chosen for
vertex $v$ (exactly one class was assigned to vertex v). Further,

$\displaystyle\sum_{f\in F}b_{vf}=\sum_{u\in
V(P_{1,v}\setminus\\{v\\})}p_{u}=0.$

This implies, at vertex $v$, it is not assigned any branching features and
$p_{u}$ = 0 for all of the ancestors $u$ of $v$. Given that $p_{u}=0$ for each
ancestor $u$ of $v$, then $\sum_{f\in F}b_{uf}=1$ by (1d). This implies each
ancestor $u$ of $v$ is assigned exactly one branching feature. Then again by
(1c), $\sum_{k\in K}w_{uk}=0$. This implies each ancestor $u$ of $v$ is not
assigned any class. Then if we look at the children of $v$ where $p_{v}=1$, by
(1d) we get,

$\displaystyle p_{c}=\sum_{f\in F}b_{cf}=\sum_{k\in K}w_{ck}=0$
$\displaystyle\leavevmode\nobreak\ \forall c\in\operatorname{CHILD}[v].$

This implies all children $c$ of $v$ are not assigned a class or branching
feature, and therefore pruned. If $v\in L$ then $\sum_{f\in F}b_{vf}=0$ by
(1e). This implies no leaf vertex is assigned to a branching feature and also
assigned exactly one class. The above statements have shown that a prediction
vertex $v\in V$ is assigned exactly one class, all of its ancestors were
assigned a single branching feature, all of its children were pruned and that
no leaf vertex can be assigned a branching feature. For each $b_{vf}=1$, then
at $v$,

$\displaystyle\sum_{g\in F\setminus\\{f\\}}b_{vg}=\sum_{u\in
V(P_{1,v})\setminus\\{v\\}}p_{u}=p_{v}=0,$

by (1d). Then for each ancestor $u$ of $v$, $\sum_{f\in F}b_{uf}=1$ by (1d).
Thus, if vertex $v$ is assigned branching feature $f\in F$, then it is not
pruned and each of its ancestors was assigned exactly one branching feature.
Then if we look at the children of $c$ of $v$ then either $\sum_{f\in
F}b_{cf}=1$ or $p_{c}=1$ by (1d), implying the children of branching vertex
$v$ are either branching or assigned a class. For each $w_{vk}=1$, $p_{v}=1$
by (1c) and follows the implications previously explicated. The following
statements have shown $\mathscr{P}_{\operatorname{FlowOCT}}$ admits a valid
assigned binary tree structure. Lastly we show
$\mathscr{P}_{\operatorname{FlowOCT}}$ admits valid paths through the tree.

For each $s^{i}_{v}=1$, by (1f) $w_{vk}=1$ where $k=y^{i}$. This implies a
datapoint classified at vertex $v$ is correct only if the vertex $v$ is
assigned the datapoint’s given class $k$. Then by constraints (2b) and (2c)
the datapoint flows $z^{i}_{a}=1$ for $a\in E(G[V(P_{1,v})])$ along the
$1,v$-path are connected and all other flows $z^{i}_{uv}\in E(G\setminus
V(P_{1,v}))=0$. Thus a correctly classified datapoint found a successful $s,t$
flow in the tree. Then by (2d) the connected flows $z^{i}_{a}$ along arcs
$a\in E(G[V(P_{1,v})])$ are branched such that the flow $z^{i}_{v,\ell(v)}$
($z^{i}_{v,r(v)}$) along the arc connecting vertex $v$ to its left (right)
child, $\ell(v)$ ($r(v)$), meant vertex $v$ was assigned some branching
feature $f\in F$ such that $x^{i}_{f}=0\leavevmode\nobreak\ (x^{i}_{f}=1)$. In
short, this implies connected flows $z^{i}_{a}$ of a datapoint $i\in I$ are
such that the flow’s left, right branching corresponds to features assigned to
branching vertices of the tree and the datapoint’s feature set values. Point
$p^{*}$ is an optimal classification tree because it satisfies (1a), and the
maximal number of training datapoints were correctly classified by the tree.
This complete the proof.

Now we prove Theorem 4.12.

###### Proof 4.14

Proof of Theorem 4.12. Let $p^{*}$ be a point that represents an optimal
binary classification tree trained by a binary encoded, discrete class
dataset, $I\coloneqq\\{x^{i},y^{i}\\}_{i\in|N|}$. We must show
$p^{*}=(b,w,p,s,q)$ is in $\mathscr{P}_{\operatorname{CUT2}}$. Given that
$p^{*}$ is a binary tree starting at the root find the deepest classification
vertex at depth $h$. We will assume the tree is of depth $h$. Enumerate
vertices starting from the root of the tree, given number 1, until $2^{h+1}-1$
ensuring the left, right children of vertex $v$ are labeled
$2v,\leavevmode\nobreak\ 2v+1$, respectively. Further, if a vertex is the
child of a classification vertex, assume it still exists and is pruned; assume
the same for children of pruned vertices. Denote leaf set $L$ as vertices
whose label is in $[2^{h},\leavevmode\nobreak\ 2^{h+1}-1]$, all other vertices
as branching set $B\coloneqq[1,\leavevmode\nobreak\ 2^{h}-1]$, and $V=B\cup
L$. For each classification vertex labeled $v$ with class $k\in K$ denote
binary variables $w_{vk}=p_{v}=1$ and binary variables $w_{vj}=b_{vf}=0$ for
every feature $f\in F$ and $j\in K\setminus\\{k\\}$, where $F$ and $K$ are the
set of training features and classes, respectively. Similarly for every vertex
labeled $v$ with branching feature $f$ we denote binary variable $b_{vf}=1$
and $w_{vk}=b_{vg}=p_{v}=0$ for every class $k\in K$ and $g\in
F\setminus\\{f\\}$. For every pruned vertex labeled $v$ we denote binary
variable $p_{v}=0$ and $w_{vk}=b_{vf}=0$ for every feature $f\in F$ and $k\in
K$. For every datapoint $i$ in training set $I$ starting at the root with
label $1$ we denote binary variable $q^{i}_{1}=1$. We then branch left right
using the $x^{i}_{f}$ binary value given to the feature of the branching
vertex $v$. From there we denote binary variables $q^{i}_{v}=1$ for every
vertex $v$ visited by $i$. All other vertices $v^{\prime}\in
V\setminus\\{v\\}$ not visited have binary variables $q^{i}_{v^{\prime}}=0$.
When datapoint $i$ reaches a classification vertex $u$, if it is correctly
assigned we denote binary variable $s^{i}_{u}=1$, else $s^{i}_{u}=0$. We also
denote binary variables $s^{i}_{u^{\prime}}=0$ for every $u^{\prime}\in
V\setminus\\{u\\}$.

For every vertex $v\in V$ with $w_{vk}=1$ for some $k\in K$, since
$w_{vj}=b_{vf}=0$ for every class $j\in K\setminus\\{k\\}$ and feature $f\in
F$ (and $p_{v}=1$), vertex $v$ satisfies constraints (1c) and (1d). We assume
$p^{*}$ is a classification tree, thus for every vertex $v\in L$, $v$ must be
assigned some class $k\in K$ or pruned. If some $v\in L$ is assigned a class
$k$, then $w_{vk}=1$ and we have the above. Further all such $v\in L$ satisfy
constraints (1e). For every vertex $v\in V$ with $b_{vf}=1$ for some $f\in F$,
since

$\displaystyle b_{vg}=w_{vk}=p_{v}=0$ $\displaystyle\leavevmode\nobreak\
\forall g\in F\setminus\\{f\\},\leavevmode\nobreak\ \forall k\in K,$

every such $v$ satisfies constraints (1c) and (1d). There are no such $v\in L$
with $b_{vf}=1$ for any $f\in F$ since $p^{*}$ is a classification tree and
thus constraints (1e) are also satisfied. For each $v$ with $p_{v}=1$, then
$w_{vk}=1$ for some $k\in K$ and follows the above. For each $p_{v}=0$ then
$b_{vf}=1$ for some $f\in F$ or $w_{vk}=0$ for all $k\in K$ each following the
above.

Here we have shown, $p^{*}\in\mathscr{P}_{\operatorname{BASE}}$. To show
$p^{*}\in\mathscr{P}_{\operatorname{CUT2}}$ next we must show it satisfies our
$\operatorname{CUT2}$ connectivity constraints. For each datapoint $i\in I$
there will exist a connected $1,v$-path to some terminal vertex $v$, denoted
$P_{1,v}$, using the feature set of $x^{i}$. Let $q^{i}_{c}=1$ for every $c\in
P_{1,v}$. Further, since binary variables $b,\leavevmode\nobreak\
w,\leavevmode\nobreak\ p$ satisfy constraints (1c)-(1e) and branching are done
using the values of $x^{i}$, then,

$\displaystyle q^{i}_{\ell(c)}\leq\sum_{f\in
F:x^{i}_{f}=0}b_{cf}\leq\sum_{f\in F}b_{cf}\leq 1,$ $\displaystyle
q^{i}_{r(c)}\leq\sum_{f\in F:x^{i}_{f}=1}b_{cf}\leq\sum_{f\in F}b_{cf}\leq 1,$

for each vertex $c\in P_{1,v}$ and for every datapoint $i\in I$. Thus,
constraints (14c) are satisfied for every $i\in I$ and $v\in V$. At terminal
vertex $v$ assigned to class $k$, if datapoint $i$ is correctly classified,
then $s^{i}_{v}=w_{vk}=1$. Further, $k=y^{i}$ and $s^{i}_{n}=0$ for every
$n\in V\setminus\\{v\\}$, satisfying constraints (1f). Terminal vertex $v$ was
reached through a connected path for each datapoint $i\in I$. Thus,
$s^{i}_{v}\leq q^{i}_{c}$ for every $c\in P_{v}$ because
$s^{i}_{v}=q^{i}_{c}=1$ at $v$ and every $c\in P_{v}$; satisfying constraints
(14b). From our labeling of binary variables $s^{i}_{n}=0$ for every $n\in
V\setminus\\{v\\}$ which implies

$\displaystyle s^{i}_{v}+\sum_{u\in\operatorname{CHILD}(V)}s^{i}_{u}\leq
s^{i}_{v}+\sum_{u\in V\setminus\\{v\\}}s^{i}_{u}=\sum_{v\in V}s^{i}_{v}=1$

thereby satisfying constraints (14d).

Lastly, because we assume our point $p^{*}$ to be an optimal classification
tree, features $f\in F$ and classes $k\in K$ were assigned to maximize the
number of correctly classified datapoints. In turn $\sum_{i\in I}\sum_{v\in
V}s^{i}_{v}$ is maximal satisfying objective (1a). This completes the proof.

##  5 Computational Experiments

Here we provide experiments on publicly available datasets to benchmark our
four proposed models ($\operatorname{MCF1}$, $\operatorname{MCF2}$,
$\operatorname{CUT1}$, $\operatorname{CUT2}$) against 4 approaches from the
literature ($\operatorname{FlowOCT}$, its Benders’ decomposition
$\operatorname{BendersOCT}$, and two forms of CART).

###  5.1 Experimental Setup

We run all experiments on an Intel(R) Core(TM) i7-9800X CPU (3.8Ghz, 19.25MB,
165W) using 1 core and 16GB RAM. Code is written in Python 3.6 or above. The
$\operatorname{MILO}$ formulations are solved using Gurobi 9.5. We consider a
time limit of 3600 seconds for all of our experiments. Datasets are publicly
available at http://archive.ics.uci.edu/ml/index.php and code is available at
https://github.com/brandalston/OBCT.

We use 13 datasets from the UCI ML repository. For each dataset we create 5
random 75-25% train-test splits. We do not consider the second objective
function (1b), minimizing the number of branching vertices, except for the
case of the Pareto frontiers of Figure 5.2. For height $h\in\\{2,3,4,5\\}$ we
train a decision tree using each model and report various metrics including
out-of-sample accuracy, in-sample optimality gap, solution-time, and in-sample
accuracy. No warm starts are used unless otherwise indicated.
$\operatorname{FlowOCT}$ and $\operatorname{BendersOCT}$ instances have a
$\lambda$ value of zero. Both CART models use the Gini index as the splitting
criterion and max depth of $h$. The second form, CARTstr, also uses singular
features at branching vertices and at most $2^{h}$ leaves.

Datasets with size $|I|$, number of encoded features $|F|$, and classes $|K|$.
Dataset $|I|$ $|F|$ $|K|$ soybean-small 47 45 4 monk3 122 15 2 monk1 124 15 2
hayes-roth 132 15 3 monk2 169 15 2 house-votes-84 232 16 2 spect 267 22 2
breast-cancer 277 38 2 balance-scale 625 20 3 tic-tac-toe 958 27 2
car_evaluation 1728 20 4 kr-vs-kp 3196 38 2 fico_binary 10459 19 2

###  5.2 Results

_MILO Formulations Comparison_. Table LABEL:tab:timegap summarizes the MILO
formulations in sample optimization performance. Evaluation of only flow-based
formulations, we see models $\operatorname{MCF1}$ and $\operatorname{MCF2}$
outperform $\operatorname{FlowOCT}$ in 37 out of 52 possible instances in
either solution time or optimality gap. Further, if we extend the comparisons
of $\operatorname{FlowOCT}$ to cut-based models $\operatorname{CUT1}$ and
$\operatorname{CUT2}$ we see an increase to 43 of 52 possible instances where
our models outperform $\operatorname{FlowOCT}$, highlighting the strength of
formulations $\operatorname{CUT1}$ and $\operatorname{CUT2}$. The average
speedup of our models over $\operatorname{FlowOCT}$ is 2.80X where as
$\operatorname{FlowOCT}$ over ours is only 1.28X. When we compare the Benders’
decomposition we see that our models perform best in 24 out of 52 possible
times. Our models have an average speedup of 1.58X over
$\operatorname{BendersOCT}$, while the $\operatorname{BendersOCT}$ average
speedup over our models is 2.47X. Complete tables for time and in-sample
optimality gap are listed in Appendix 8, Tables LABEL:tab:fulltime and
LABEL:tab:fullgap, respectively. Lastly we observe that for larger trees,
($h=4,5$), or larger datasets, ($|I|>500$), we see that models
$\operatorname{CUT1}$ and $\operatorname{CUT2}$ perform well highlighting the
strength of cut constraints that are added on-the-fly; $\operatorname{MCF2}$
remains competitive in such instances as it is a full model. As expected,
greedy formulations CART and CARTstr are very fast.

_Test Accuracy Comparison_. Table LABEL:tab:accuracy summarizes the MILO
models out-of-sample accuracy performance. Comparing $\operatorname{MILO}$
formulations, we see that FlowOCT outperforms our models in only 9 out of 52
possible instances, with the maximum being a 8% difference and on average less
than 2% variation. Extending comparisons to $\operatorname{BendersOCT}$ there
are 4 additional instances in which FlowOCT or $\operatorname{BendersOCT}$
outperforms our models. The maximum difference increases to 20% and on average
to roughly 4% due to $\operatorname{BendersOCT}$ finding a solution within the
time limit and our models reporting gap. Additional results for in-sample
accuracy are listed in Appendix 8, Table LABEL:tab:inaccuracy. Our models are
competitive against CART, both when optimality is reached or when gap is
reported. Applying a sparse tree structure to CART decreases accuracy, but the
same sparse structure has no effect in our $\operatorname{MILO}$ models.

Figure 5.2 shows the strength of taking a biobjective approach. Providing an
upper bound on the number of branching vertices, simultaneously reducing the
size of the optimization problem and controlling sparsity in the tree, leads
to competitive accuracy performance. For the same number of maximum branching
vertices our models, on average, have better out-of-sample accuracy than
$\operatorname{FlowOCT}$. Models $\operatorname{MCF2},\operatorname{CUT1}$,
and $\operatorname{CUT2}$ perform well when the size of the tree increases, as
expected. Lastly, we confirm the observations of Murthy (2004) that large
trees perform inferior to smaller trees.

_Cut Constraints Comparison_. Tables LABEL:tab:cut1table and
LABEL:tab:cut2table highlight on-the-fly introduction of the cut constraints
(13b) and (14b) in models $\operatorname{CUT1}$ and $\operatorname{CUT2}$,
respectively, leads to better solution time or in-sample optimality gap.
Speedup of up to $\sim$3X for even large size instances. Fischetti et al.
(2017) noted adding too many fractional cuts may lead to slower performance
and Tables LABEL:tab:cut1table and LABEL:tab:cut2table confirms this result
for optimal binary decision tree formulations as instances are reported with a
$\sim$20X slowdown. While there are improvements using on-the-fly cuts for
large trees, our testing does not suggest a convention on which procedure is
most effective. Note that cuts obtained by solving the fractional separation
problem are most effective for smaller trees.

Table 1: Average solution time (in seconds) or in-sample optimality gap, (in parentheses), if the time limit (3600s) was reached. Best in bold (* if $\operatorname{BendersOCT}$). Dataset | $D_{h}$ | FlowOCT | $\operatorname{MCF1}$ | $\operatorname{MCF2}$ | $\operatorname{CUT1}$ | $\operatorname{CUT2}$ | $\operatorname{BendersOCT}$ | CART |  CARTstr
---|---|---|---|---|---|---|---|---|---
soybean-small | 2 | 0.08 | 0.10 | 0.06 | 0.04 | 0.07 | 0.20 |  $<$0.01 |  $<$0.01
3 | 0.16 | 0.08 | 0.09 | 0.08 | 0.08 | 0.20 |  $<$0.01 |  $<$0.01
4 | 0.33 | 0.28 | 0.27 | 0.22 | 0.22 | 0.36 |  $<$0.01 |  $<$0.01
5 | 0.65 | 0.52 | 0.65 | 0.49 | 0.50 | 0.49* |  $<$0.01 |  $<$0.01
monk3 | 2 | 0.51 | 0.94 | 1.02 | 0.56 | 0.56 | 0.23* |  $<$0.01 |  $<$0.01
3 | 91.98 | 105.15 | 92.57 | 66.25 | 91.99 | 15.70* |  $<$0.01 |  $<$0.01
4 | 2210.76 | 2186.47 | 2197.56 | 1733.84 | 1924.94 | 2381.33 |  $<$0.01 |  $<$0.01
5 | 187.22 | 219.00 | 142.03 | 79.16 | 136.59 | 42.62* |  $<$0.01 |  $<$0.01
monk1 | 2 | 0.74 | 1.68 | 1.12 | 0.67 | 0.73 | 0.48* |  $<$0.01 |  $<$0.01
3 | 32.65 | 35.65 | 35.19 | 25.44 | 25.73 | 4.33* |  $<$0.01 |  $<$0.01
4 | 15.89 | 22.63 | 8.92 | 9.87 | 13.01 | 2.13* |  $<$0.01 |  $<$0.01
5 | 8.46 | 16.60 | 13.78 | 12.06 | 12.52 | 1.51* |  $<$0.01 |  $<$0.01
hayes-roth | 2 | 0.69 | 2.69 | 1.01 | 0.62 | 0.62 | 0.83 |  $<$0.01 |  $<$0.01
3 | 13.86 | 59.02 | 31.50 | 40.76 | 26.83 | 7.86* |  $<$0.01 |  $<$0.01
4 | 2430.02 | 1819.18 | 1415.03 | 1512.81 | 1270.11 | 2422.33 |  $<$0.01 |  $<$0.01
5 | (8.86) | (9.53) | (8.66) | (9.12) | (9.82) | (9.06) |  $<$0.01 |  $<$0.01
monk2 | 2 | 6.76 | 5.83 | 3.40 | 1.87 | 1.92 | 3.12 |  $<$0.01 |  $<$0.01
3 | 2935.01 | 1898.05 | 469.60 | 1014.42 | 804.51 | 1205.76 |  $<$0.01 |  $<$0.01
4 | (17.23) | (18.36) | (17.43) | (18.05) | (18.6) | (12.95)* |  $<$0.01 |  $<$0.01
5 | (11.71) | (9.20) | (8.48) | (9.20) | (8.45) | (10.38) |  $<$0.01 |  $<$0.01
house-votes-84 | 2 | 0.76 | 2.97 | 1.97 | 1.06 | 1.07 | 0.48* |  $<$0.01 |  $<$0.01
3 | 200.91 | 167.30 | 127.05 | 173.64 | 133.14 | 80.30* |  $<$0.01 |  $<$0.01
4 | 2882.22 | 2169.07 | 1087.32 | 1144.08 | 1209.22 | 2882.02 |  $<$0.01 |  $<$0.01
5 | 471.55 | 62.14 | 76.84 | 115.90 | 116.2 | 555.25 |  $<$0.01 |  $<$0.01
spect | 2 | 9.97 | 15.90 | 13.96 | 2.84 | 2.63 | 4.14 |  $<$0.01 |  $<$0.01
3 | 2790.05 | 1760.49 | 1736.55 | 942.73 | 1385.65 | 2162.11 |  $<$0.01 |  $<$0.01
4 | (35.36) | (4.70) | (4.48) | (4.59) | (4.36) | (4.21)* |  $<$0.01 |  $<$0.01
5 | (55.49) | (4.61) | (5.85) | (5.30) | (4.17) | (4.87) |  $<$0.01 |  $<$0.01
breast-cancer | 2 | 23.69 | 45.94 | 7.79 | 7.68 | 7.43 | 17.19 |  $<$0.01 |  $<$0.01
3 | (73.58) | (17.99) | (13.22) | (12.98) | (13.91) | (12.07)* |  $<$0.01 |  $<$0.01
4 | (16.05) | (17.11) | (15.27) | (15.52) | (15.02) | (15.67) |  $<$0.01 |  $<$0.01
5 | (11.68) | (10.37) | (11.69) | (10.15) | (9.90) | (11.34) |  $<$0.01 |  $<$0.01
balance-scale | 2 | 10.51 | 21.68 | 17.16 | 7.29 | 7.23 | 6.60* |  $<$0.01 |  $<$0.01
3 | 1863.60 | 1651.92 | 1384.10 | 1235.88 | 1232.90 | 895.25* |  $<$0.01 |  $<$0.01
4 | (97.26) | (21.67) | (20.67) | (18.36) | (19.26) | (9.88)* |  $<$0.01 |  $<$0.01
5 | (100) | (21.44) | (21.12) | (21.32) | (21.56) | (21.63) |  $<$0.01 |  $<$0.01
tic-tac-toe | 2 | 490.04 | 327.18 | 96.10 | 93.31 | 104.08 | 139.20 |  $<$0.01 |  $<$0.01
3 | (100) | (30.84) | (29.01) | (28.45) | (29.36) | (18.57)* |  $<$0.01 |  $<$0.01
4 | (100) | (22.21) | (19.52) | (19.20) | (19.75) | (19.75) |  $<$0.01 |  $<$0.01
5 | (100) | (13.04) | (13.00) | (16.27) | (14.81) | (14.24) |  $<$0.01 |  $<$0.01
car_evaluation | 2 | 83.46 | 111.03 | 45.28 | 38.99 | 35.97 | 32.08* |  $<$0.01 |  $<$0.01
3 | (78.89) | (23.29) | (18.32) | (18.26) | (17.5) | (5.07)* |  $<$0.01 |  $<$0.01
4 | (100) | (28.27) | (21.44) | (22.73) | (21.9) | (20.65)* |  $<$0.01 |  $<$0.01
5 | (83.71) | (40.15) | (32.01) | (39.44) | (34.43) | (18.03)* |  $<$0.01 |  $<$0.01
kr-vs-kp | 2 | 609.73 | 3244.23 | 1049.04 | 1209.25 | 1220.4 | 420.01* |  $<$0.01 |  $<$0.01
3 | (19.97) | (42.4) | (17.16) | (15.56) | (18.52) | (8.56)* |  $<$0.01 |  $<$0.01
4 | (27.98) | (91.94) | (41.53) | (45.89) | (42.85) | (12.6) |  $<$0.01 |  $<$0.01
5 | (25.56) | (57.43) | (45.86) | (34.53) | (43.39) | (5.36)* |  $<$0.01 |  $<$0.01
fico_binary | 2 | 944.53 | (25.05) | 858.20 | 955.18 | 1408.68 | 2414.30 |  $<$0.01 |  $<$0.01
3 | (98.31) | (39.50) | (39.51) | (41.47) | (41.43) | (39.95) |  $<$0.01 |  $<$0.01
4 | (99.57) |  ($>100$) | (60.95) |  ($>100$) |  ($>100$) | (41.48)* |  $<$0.01 |  $<$0.01
5 | (40.71) |  ($>100$) |  ($>100$) |  ($>100$) |  ($>100$) | (40.64)* |  $<$0.01 |  $<$0.01
Table 2: Average out-of-sample accuracy (%). Best in bold (* if $\operatorname{BendersOCT}$ or CART). Dataset | $D_{h}$ | FlowOCT | $\operatorname{MCF1}$ | $\operatorname{MCF2}$ | $\operatorname{CUT1}$ | $\operatorname{CUT2}$ | $\operatorname{BendersOCT}$ | CART |  CARTstr
---|---|---|---|---|---|---|---|---|---
soybean-small | 2 | 100 | 98.33 | 100 | 100 | 100 | 98.33 | 68.33 | 46.67
3 | 98.33 | 98.33 | 96.67 | 98.33 | 98.33 | 95.00 | 100* | 55.00
4 | 98.33 | 96.67 | 98.33 | 98.33 | 96.67 | 95.00 | 96.67 | 76.67
5 | 98.33 | 100 | 96.67 | 96.67 | 100 | 90.00 | 98.33 | 90.00
monk3 | 2 | 94.19 | 94.19 | 94.19 | 94.19 | 94.19 | 94.19* | 94.19* | 61.29
3 | 92.90 | 92.26 | 92.26 | 92.90 | 92.90 | 92.26 | 94.19* | 62.58
4 | 92.26 | 89.03 | 89.68 | 90.32 | 92.26 | 90.97 | 92.90* | 63.87
5 | 88.39 | 89.03 | 89.68 | 91.61 | 87.74 | 87.10 | 91.61* | 70.32
monk1 | 2 | 74.84 | 74.84 | 74.84 | 74.84 | 74.84 | 74.84* | 73.55 | 50.97
3 | 84.52 | 87.10 | 85.81 | 86.45 | 87.10 | 87.74* | 82.58 | 54.84
4 | 98.06 | 100 | 100 | 100 | 100 | 100* | 81.29 | 67.10
5 | 100 | 98.71 | 100 | 100 | 100 | 100* | 79.35 | 69.68
hayes-roth | 2 | 44.24 | 44.24 | 44.24 | 44.24 | 44.24 | 44.24 | 46.67* | 37.58
3 | 56.97 | 56.36 | 56.36 | 56.36 | 56.36 | 56.36 | 53.33 | 47.27
4 | 67.27 | 64.85 | 66.06 | 67.27 | 67.27 | 65.45 | 60.61 | 47.88
5 | 70.91 | 64.24 | 70.91 | 75.76 | 75.76 | 68.48 | 64.24 | 57.58
monk2 | 2 | 54.42 | 55.81 | 55.81 | 55.81 | 56.28 | 56.28 | 58.60* | 57.21
3 | 68.84 | 64.65 | 67.44 | 69.3 | 69.77 | 66.05 | 58.14 | 57.21
4 | 56.74 | 62.33 | 61.86 | 65.58 | 65.12 | 66.05* | 58.14 | 52.56
5 | 58.14 | 65.58 | 65.58 | 64.65 | 64.65 | 59.07 | 63.72 | 52.56
house-votes-84 | 2 | 95.52 | 95.52 | 95.52 | 95.52 | 95.52 | 95.52 | 96.55* | 81.03
3 | 93.10 | 92.76 | 92.76 | 93.10 | 92.76 | 92.41 | 93.45* | 86.55
4 | 95.86 | 94.83 | 96.21 | 96.55 | 96.55 | 95.17 | 94.48 | 88.62
5 | 93.79 | 93.79 | 95.17 | 95.86 | 95.52 | 93.79 | 95.17 | 87.59
spect | 2 | 77.01 | 77.01 | 77.01 | 77.01 | 77.01 | 77.01 | 77.01 | 80.30*
3 | 77.31 | 77.61 | 77.61 | 77.61 | 77.61 | 77.31 | 78.21* | 77.61
4 | 80.30 | 77.61 | 81.19 | 79.70 | 80.00 | 79.40 | 77.01 | 80.30
5 | 81.19 | 77.31 | 80.00 | 79.40 | 80.00 | 77.91 | 80.00 | 76.72
breast-cancer | 2 | 74.00 | 72.00 | 73.14 | 72.57 | 72.57 | 72.00 | 75.71* | 69.43
3 | 71.43 | 69.71 | 71.71 | 69.71 | 72.00 | 67.43 | 71.43 | 70.86
4 | 68.57 | 69.14 | 69.43 | 70.71 | 71.07 | 68.86 | 71.71* | 70.86
5 | 70.86 | 70.00 | 69.43 | 71.43 | 71.43 | 69.43 | 68.86 | 70.86
balance-scale | 2 | 64.20 | 64.20 | 64.20 | 64.20 | 64.20 | 64.20* | 62.80 | 53.50
3 | 67.64 | 67.26 | 67.64 | 67.64 | 67.64 | 67.64* | 65.61 | 53.89
4 | 70.57 | 70.83 | 71.72 | 72.48 | 71.46 | 69.30 | 65.48 | 57.58
5 | 73.12 | 72.48 | 71.34 | 73.25 | 73.25 | 69.30 | 69.81 | 60.25
tic-tac-toe | 2 | 68.58 | 68.58 | 68.58 | 68.50 | 68.58 | 68.33 | 69.67* | 67.08
3 | 73.17 | 74.08 | 74.33 | 74.08 | 74.33 | 73.75 | 73.58 | 68.08
4 | 80.42 | 76.17 | 80.92 | 80.50 | 80.50 | 81.33 | 82.92* | 69.25
5 | 81.17 | 82.00 | 84.92 | 81.75 | 84.25 | 84.75 | 88.92* | 69.75
car_evaluation | 2 | 77.78 | 77.78 | 77.78 | 77.78 | 77.78 | 77.78* | 77.78* | 69.81
3 | 78.43 | 78.19 | 78.52 | 78.94 | 78.94 | 78.52 | 79.31* | 70.00
4 | 81.85 | 78.15 | 80.51 | 80.28 | 80.23 | 80.79 | 80.56 | 71.53
5 | 83.24 | 72.08 | 75.60 | 71.25 | 75.00 | 82.41 | 86.02* | 70.09
kr-vs-kp | 2 | 86.78 | 86.78 | 86.78 | 86.78 | 86.78 | 86.78* | 77.15 | 57.72
3 | 83.65 | 72.19 | 84.73 | 86.53 | 83.88 | 92.17* | 89.89 | 63.30
4 | 78.50 | 70.26 | 64.86 | 67.98 | 69.56 | 89.04 | 93.94* | 59.42
5 | 79.67 | 64.26 | 67.93 | 74.64 | 69.31 | 94.72* | 93.94 | 64.13
fico_binary | 2 | 70.73 | 70.80 | 70.73 | 70.73 | 70.73 | 70.73 | 68.88 | 60.29
3 | 70.97 | 70.88 | 70.97 | 69.76 | 69.77 | 70.65 | 70.07 | 66.07
4 | 70.20 | 53.06 | 61.93 | 53.06 | 53.06 | 70.11 | 70.74* | 68.59
5 | 68.82 | 53.06 | 61.93 | 53.06 | 53.06 | 70.02 | 70.93* | 68.28

Pareto Frontiers for monk1, monk3, house-votes-84, and soybean-small datasets.
Dominating points are in bold.

Figure 5.2 summarizes our experiments with all $\operatorname{MILO}$
formulations and _both_ objective functions (1a) and (1b). We maximize
objective function (1a) while objective function (1b) is considered as a
constraint on the number of branching vertices. Shown are out-of-sample
accuracy (%) average ($y$ axis) vs number of branching decisions ($x$ axis)
and trend lines. Dominating and dominated Pareto points are illustrated in
opaque and transparent colors, respectively. The solution for $k$ branching
vertices is used as a warm-start for $k+1$ branching vertices for all models.
Observe that $\operatorname{MCF2}$, $\operatorname{CUT1}$,
$\operatorname{CUT2}$ are the superior models when the maximum number of
branching vertices is large. $\operatorname{MCF2}$ generally performs well due
to its strong LO relaxation and the fact the entire model is fed upfront,
compared to lazy constraints for $\operatorname{CUT1}$ and
$\operatorname{CUT2}$. Further one can see our models achieve higher out of
sample accuracy compared to $\operatorname{FlowOCT}$ with the same or fewer
branching vertices (particularly in monk3 and house-votes-84). Also the Pareto
frontiers confirm in $\operatorname{MILO}$ formulations of optimal binary
decision trees that larger trees do not always result in better out-of-sample
performance.

For cut-based formulations $\operatorname{CUT1}$ and $\operatorname{CUT2}$, we
consider a number of variations on implementing cut constraints (13b) and
(14b), respectively. We implement integral cut constraints using Gurobi lazy
parameter = 3, constraints that cut off the relaxation solution at the root
node are pulled in. We also introduce all integral cut constraints up front.
Then we consider the cut constraints at fractional points in the branch and
bound tree with three variations. The first type adds all violating cuts for a
datapoint in the $1,v$-path of a terminal vertex $v$. The second type adds the
first found violating cut in the $1,v$-path. The third type adds the most
violating cut in the $1,v$-path (if more than one exists, only the cut closest
to the root vertex of $G_{h}$ is added). These user cuts consider an epislon
comparison of $\epsilon=10^{-4}$. We consider three variations on violating
cuts due to Fischetti et al. (2017) who note adding too many fractional cuts
may slow down solution time of $\operatorname{MILO}$ formulations for the
Steiner tree problem, which is highly related to decision trees. As a result
we consider a heavy set of user cuts (all violating cuts) and two light sets
of user cuts (first found and most violating). An example of the three types
of cuts is shown in Figure 6.

$a$$q^{i}_{a}=0.75$$b$$q^{i}_{b}=0.25$$c$$q^{i}_{c}=0.5$$v$$q^{i}_{v}=0.25$$s^{i}_{v}=0.75$ALL
(1)$1^{\text{st}}$ Found (2)Most Violating (3) Figure 6: Let $a,b,c$, and $v$
be nodes selected on the $1,v$-path of datapoint $i\in I$ at a fractional
point in the branch and bound tree with $s^{i}_{v}$ and $q^{i}_{u}$ for $u\in
P_{v}$ as defined. The 3 types of fractional user cuts are in solid colored
arrows (the dotted line is a most violating cut considered but not added).

Tables LABEL:tab:cut1table and LABEL:tab:cut2table compare adding all integral
cut constraints (13b) and (14b), respectively, upfront vs introducing them at
the root node of the branch and bound tree or with the fractional cuts
outlined above. The ALL column contains the solution time or gap of the CUT
model with all integral cut constraints introduced upfront (i.e., the full
model). The other columns represent solution time or gap ratios to the ALL
column. Decreases (increases) in solution time or gap are indicated in bold
(light). Both tables highlight adding our cut constraints on-the-fly, at
fractional or integral points in the branch and bound tree, does help improve
solution time over adding all cut constraints upfront. However, it is still
feasible to introduce all cut constraints upfront with large datasets for
efficient solution times. Results shown only consider fractional cuts at the
root node of the branch and bound tree as our testing showed marginal
improvement when cuts were added at all nodes of the branch and bound tree.

Table 3: $\operatorname{CUT1}$ fractional cuts comparison. ALL represents integral constraints introduced upfront and their solution time (gap). Decreases (increases) in the solution time or gap ratio are indicated in bold (light) for other columns. LAZY represents constraints introduced to cut off the relaxation solution at the root node of the branch and bound tree. Dataset | $D_{h}$ | ALL | LAZY | FRAC-1 | FRAC-2 | FRAC-3
---|---|---|---|---|---|---
soybean-small | 2 | 0.04 | 1.83 | 2.23 | 2.21 | 2.23
3 | 0.08 | 2.56 | 1.99 | 3.60 | 3.67
4 | 0.22 | 2.11 | 2.73 | 2.34 | 2.35
5 | 0.49 | 2.47 | 2.67 | 2.42 | 2.44
monk3 | 2 | 1.52 | 0.37 | 0.38 | 0.38 | 0.38
3 | 66.25 | 1.22 | 1.13 | 1.86 | 1.85
4 | 2222.62 | 0.78 | 0.91 | 0.89 | 0.89
5 | 253.98 | 0.48 | 0.31 | 0.50 | 0.51
monk1 | 2 | 1.66 | 0.45 | 0.41 | 0.41 | 0.41
3 | 34.63 | 0.73 | 0.91 | 1.00 | 1.00
4 | 9.87 | 1.29 | 1.24 | 1.90 | 1.90
5 | 13.42 | 0.90 | 1.30 | 0.98 | 0.98
hayes-roth | 2 | 1.28 | 0.48 | 0.50 | 0.50 | 0.50
3 | 42.02 | 1.09 | 1.07 | 0.97 | 0.97
4 | 1512.81 | 1.84 | 1.62 | 1.65 | 1.94
5 | (9.12) | 1.10 | 1.02 | 1.13 | 1.16
monk2 | 2 | 3.64 | 0.53 | 0.52 | 0.52 | 0.51
3 | 1014.42 | 1.24 | 1.42 | 1.11 | 1.11
4 | (18.05) | 1.06 | 1.02 | 1.12 | 1.13
5 | (10.38) | 0.95 | 0.97 | 0.89 | 0.92
house-votes-84 | 2 | 2.89 | 0.37 | 0.37 | 0.37 | 0.37
3 | 173.64 | 1.46 | 1.54 | 1.67 | 1.66
4 | 1625.82 | 1.07 | 0.70 | 0.80 | 0.80
5 | 115.90 | 1.37 | 1.22 | 1.07 | 1.07
spect | 2 | 13.42 | 0.21 | 0.23 | 0.24 | 0.24
3 | 1670.76 | 0.73 | 0.56 | 0.62 | 0.77
4 | (4.59) | 1.15 | 1.15 | 1.10 | 1.12
5 | (5.30) | 1.15 | 1.02 | 1.06 | 1.06
breast-cancer | 2 | 18.72 | 0.75 | 0.41 | 0.41 | 0.41
3 | (12.98) | 1.22 | 1.17 | 1.23 | 1.23
4 | (15.52) | 1.03 | 1.07 | 1.01 | 1.01
5 | (10.98) | 0.92 | 1.04 | 1.01 | 1.01
balance-scale | 2 | 19.31 | 0.38 | 0.40 | 0.40 | 0.40
3 | 1235.88 | 1.87 | 1.62 | 1.61 | 1.61
4 | (18.36) | 1.21 | 1.13 | 1.11 | 1.18
5 | (21.32) | 1.03 | 1.02 | 1.00 | 1.01
tic-tac-toe | 2 | 283.51 | 0.37 | 0.33 | 0.33 | 0.33
3 | (28.45) | 1.05 | 1.03 | 1.05 | 1.05
4 | (20.33) | 0.97 | 1.02 | 0.94 | 0.94
5 | (16.27) | 1.16 | 1.36 | 1.17 | 1.11
car_evaluation | 2 | 38.99 | 1.23 | 1.27 | 1.27 | 1.26
3 | (19.46) | 0.96 | 1.10 | 0.95 | 0.94
4 | (22.73) | 1.09 | 1.10 | 1.12 | 1.12
5 | (39.44) | 3.98 | 1.13 | 1.16 | 1.91
kr-vs-kp | 2 | 2850.18 | 0.42 | 0.70 | 0.69 | 0.77
3 | (39.55) | 0.40 | 0.39 | 0.42 | 0.42
4 | (46.16) | 1.00 | 1.00 | 0.99 | .99
5 | (34.53) | 1.38 | 25.95 | 26.39 | 1.83
fico_binary | 2 | 955.18 | 3.77 | 3.58 | 3.73 | 3.71
3 | (41.47) | 5.30 | 6.70 | 7.35 | 7.35
4 | (106.89) | 3.68 | 3.69 | 3.68 | 3.68
5 | (106.94) | 60.45 | 91.69 | 52.28 | 35.67
Table 4: $\operatorname{CUT2}$ fractional cuts comparison. ALL represents integral constraints introduced upfront and their solution time (gap). Decreases (increases) in solution time or gap ratio are indicated in bold (light) for other columns. LAZY represents constraints introduced to cut off the relaxation solution at the root node of the branch and bound tree. Dataset | $D_{h}$ | ALL | LAZY | FRAC-1 | FRAC-2 | FRAC-3
---|---|---|---|---|---|---
soybean-small | 2 | 0.07 | 2.01 | 1.03 | 1.03 | 1.05
3 | 0.08 | 2.12 | 2.93 | 2.88 | 2.89
4 | 0.22 | 2.48 | 2.72 | 2.23 | 2.21
5 | 0.50 | 2.99 | 3.30 | 2.71 | 2.71
monk3 | 2 | 1.28 | 0.44 | 0.46 | 0.45 | 0.46
3 | 114.73 | 0.80 | 0.92 | 0.97 | 0.97
4 | 2186.42 | 0.88 | 1.02 | 0.90 | 0.90
5 | 383.06 | 0.36 | 0.44 | 0.36 | 0.37
monk1 | 2 | 1.54 | 0.47 | 0.48 | 0.47 | 0.48
3 | 30.84 | 0.83 | 1.23 | 1.00 | 1.00
4 | 17.14 | 0.80 | 1.70 | 0.76 | 0.76
5 | 20.47 | 0.63 | 0.61 | 1.07 | 1.07
hayes-roth | 2 | 1.24 | 0.50 | 0.53 | 0.53 | 0.53
3 | 26.83 | 1.70 | 1.66 | 1.72 | 1.71
4 | 1270.11 | 2.12 | 2.29 | 1.63 | 1.48
5 | (9.82) | 1.05 | 1.07 | 1.05 | 1.00
monk2 | 2 | 4.01 | 0.48 | 0.49 | 0.49 | 0.49
3 | 804.51 | 1.58 | 2.03 | 1.71 | 1.71
4 | (19.74) | 1.00 | 0.96 | 0.95 | 0.94
5 | (8.45) | 1.25 | 1.27 | 1.37 | 1.40
house-votes-84 | 2 | 2.65 | 0.40 | 0.41 | 0.40 | 0.41
3 | 133.14 | 1.97 | 1.78 | 1.74 | 1.75
4 | 1861.33 | 0.93 | 0.65 | 0.71 | 0.71
5 | 116.20 | 1.39 | 1.76 | 1.95 | 1.96
spect | 2 | 12.71 | 0.21 | 0.22 | 0.24 | 0.24
3 | 1531.80 | 0.97 | 1.18 | 0.92 | 0.90
4 | (4.36) | 1.22 | 1.17 | 1.33 | 1.21
5 | (4.17) | 1.35 | 1.38 | 1.49 | 1.30
breast-cancer | 2 | 65.27 | 0.22 | 0.11 | 0.11 | 0.11
3 | (15.74) | 1.07 | 0.89 | 0.88 | 0.88
4 | (15.02) | 1.08 | 1.09 | 1.09 | 1.08
5 | (10.66) | 0.93 | 1.06 | 0.99 | 0.94
balance-scale | 2 | 16.52 | 0.44 | 0.46 | 0.46 | 0.46
3 | 1232.90 | 1.87 | 1.78 | 1.81 | 1.81
4 | (20.62) | 1.02 | 0.93 | 0.99 | 0.99
5 | (21.82) | 0.99 | 0.99 | 1.00 | 1.02
tic-tac-toe | 2 | 281.79 | 0.37 | 0.38 | 0.38 | 0.37
3 | (29.71) | 1.02 | 0.99 | 0.99 | 0.99
4 | (20.40) | 0.97 | 1.01 | 1.02 | 1.01
5 | (14.81) | 1.25 | 1.52 | 1.25 | 1.16
car_evaluation | 2 | 35.97 | 1.33 | 1.42 | 1.42 | 1.42
3 | (17.50) | 1.06 | 1.20 | 1.12 | 1.12
4 | (21.90) | 1.09 | 1.31 | 1.17 | 1.16
5 | (34.43) | 3.45 | 2.67 | 3.80 | 2.59
kr-vs-kp | 2 | 3048.5 | 0.40 | 0.50 | 0.51 | 0.49
3 | (48.67) | 0.38 | 0.38 | 0.55 | 0.57
4 | (42.85) | 1.08 | 1.08 | 1.07 | 1.06
5 | (43.39) | 1.10 | 1.07 | 1.25 | 1.25
fico_binary | 2 | 1408.68 | 2.41 | 2.40 | 2.41 | 2.40
3 | (41.43) | 4.10 | 3.35 | 4.93 | 4.93
4 | (106.73) | 3.46 | 3.36 | 3.62 | 3.49
5 | (106.86) | 5.34 | 21.95 | 21.95 | 19.98

##  6 Discussion

Here we would like to have a brief discussion on the use of
$\operatorname{MILO}$ formulations over heuristic formulations for finding
optimal binary classification trees as well as a direction for future work
related to $\operatorname{MILO}$ formulations of binary decision trees.

Observe in Table LABEL:tab:accuracy there is a drop off in out-of-sample
accuracy when you apply a sparse tree structure to CART. This same sparse tree
structure is present in our $\operatorname{MILO}$ models which achieve higher
out-of-sample accuracy than CART, in instances where optimality is reached. If
we consider instances where our models reported gap, we still have
competitive, if not higher, out-of-sample accuracy compared to CART. This
raises an important question for machine learning methods solved used
$\operatorname{MILO}$ formulations; does optimality need to be achieved? Our
models report gap in 21 instances, but CART outperforms in out-of-sample
accuracy in only a single such instance. We limit CART to $2^{h}$ leaves and a
single feature used for branching and do not consider any cost complexity
pruning or post-processing pruning techniques that would be employed to yield
a sparse tree structure with good out-of-sample performance similar to our
$\operatorname{MILO}$ models. However, if we want to find some solution
comparable to CART through our models, we simply stop the solver early;
removing any tuning procedures needed. We have not explored the natural
question to ask; what percentage gap is _good enough_ for suitable out-of-
sample performance. The Pareto frontiers in Figure 5.2 cannot be generated
using CART, as there is no way to control the final number of branching
vertices in the tree. These relatively easy to understand plots allow users to
have a quick understanding of tree complexity and its relationship to in and
out-of-sample performance.

Objective function (1b) is used as a constraint to control sparsity but can be
modified to,

$\displaystyle\sum_{v\in B}b_{v,f}\leq k$ $\displaystyle\forall f\in F,$

to further impose sparsity by limiting the use of a single feature to no more
thank $k$ times in the final tree. Regularization can also be applied by
adding constraints of the form,

$\displaystyle\sum_{i\in I}s^{i}_{v}\geq K_{min}*p_{v}$ $\displaystyle\forall
v\in V,$

which ensure each classification vertex contains at least $K_{min}$ points.
Currently we only explore a simple objective of maximizing correctly
classified nodes which does not address issues of bias, fairness, or
robustness. There is high interest in interpretable models that remain
algorithmicly unbiased (Bertsimas et al. 2019, Malik and Singh 2019, Fu et al.
2020). We have not explored dual graph or symmetry breaking approaches but
would like to in the future.

##  7 Conclusion

In this paper we propose four new mixed integer linear optimization
formulations that improve upon the recent flow-based formulation
$\operatorname{FlowOCT}$ of Aghaei et al. (2021). These novel models improve
on the linear optimization relaxation of $\operatorname{FlowOCT}$, shown
theoretically and empirically through experimental testing. An improvement in
solution time or in-sample optimality gap is observed in 43 out of 52 test
instances. Further, our models are able to outperform a tailored Benders’
decomposition of $\operatorname{FlowOCT}$ in 24 out of 52 test instances.
Lastly, we can improve solution times by adding cuts at the root node of the
branch and bound tree. Improvement in out-of-sample accuracy over
$\operatorname{FlowOCT}$ and its Benders’ decomposition is observed in 20 out
of 52 test instances. Further, our models outperform the industry standard
CART with respect to out-of-sample accuracy in 26 out of 52 instances, even
when optimality is not reached. The sparse tree structure of our models
improves interpretability without compromising accuracy. Our biobjective
approach allows for Pareto frontiers that provide succinct interpretations of
tree topology which show our models provide comparatively higher out-of-sample
accuracy, even as the tree size arbitrarily increases.

Many current heuristic and machine learning techniques may need probability
distributions of observed features, known optimal solutions, analytic
gradients, or very large training datasets that may not be readily available
for a given problem. Further, solutions may be too complex for understanding
and thereby a black-box model. We have shown $\operatorname{MILO}$
formulations yield strong out-of-sample performance trees with interpretable
structures obtained from either small or large datasets. Pareto frontiers,
reflecting trees with predetermined sparse structures, show good out-of-sample
test performance but arbitrarily adding branching features decreases accuracy.
Our $\operatorname{MILO}$ formulations with cut constraints that are added on-
the-fly improve solution time and scale. Metrics measuring fairness, disparate
treatment, or more complex non-convex functions can be used in-lieu of our
simple objective function of maximizing correctly classified points;
highlighting the flexibility of $\operatorname{MILO}$ models for training
decision trees. By providing a foundation for using discrete optimization for
training supervised machine learning models we further bridge the gap between
analytics, machine learning, and operations research.

## References

  * Aghaei et al. (2021) Aghaei S, Azizi MJ, Vayanos P (2021) Strong optimal classification trees. _CoRR_ abs/2103.15965.
  * Aglin et al. (2020) Aglin G, Nijssen S, Schaus P (2020) Learning optimal decision trees using caching branch-and-bound search. _Proceedings of the AAAI Conference on Artificial Intelligence_ 34(04):3146–3153.
  * Albaqami et al. (2021) Albaqami H, Hassan GM, Subasi A, Datta A (2021) Automatic detection of abnormal eeg signals using wavelet feature extraction and gradient boosting decision tree. _Biomedical Signal Processing and Control_ 70:102957.
  * Angelino et al. (2017) Angelino E, Larus-Stone N, Alabi D, Seltzer M, Rudin C (2017) Learning certifiably optimal rule lists. _Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , 35–44 (New York, NY, USA: Association for Computing Machinery).
  * Balestriero (2017) Balestriero R (2017) Neural decision trees. _ArXiv_ abs/1702.07360.
  * Balk and Elder (2000) Balk B, Elder K (2000) Combining binary decision tree and geostatistical methods to estimate snow distribution in a mountain watershed. _Water Resources Research_ 36(1):13–26.
  * Barata and Veenman (2021) Barata AP, Veenman CJ (2021) Fair tree learning. _CoRR_ abs/2110.09295.
  * Bennett (1995) Bennett K (1995) Global tree optimization: A non-greedy decision tree algorithm. _Computing Sciences and Statistics_ 26\.
  * Bennett and Mangasarian (1993) Bennett K, Mangasarian O (1993) Bilinear separation of two sets inn-space. _Computational Optimization and Applications_ 2:207–227, URL http://dx.doi.org/10.1007/BF01299449.
  * Bennett and Blue (1996) Bennett KP, Blue JA (1996) Optimal decision trees. _Rensselaer Polytechnic Institute Math Report_ 214:24.
  * Bertsimas et al. (2021) Bertsimas D, Cory-Wright R, Pauphilet J (2021) Mixed-projection conic optimization: A new paradigm for modeling rank constraints. _Operations Research_ .
  * Bertsimas and Dunn (2017) Bertsimas D, Dunn J (2017) Optimal classification trees. _Machine Learning_ 106(7):1039–1082.
  * Bertsimas et al. (2019) Bertsimas D, Dunn J, Mundru N (2019) Optimal prescriptive trees. _INFORMS Journal on Optimization_ 1(2):164–183.
  * Bertsimas and Shioda (2007) Bertsimas D, Shioda R (2007) Classification and regression via integer optimization. _Operations Research_ 55(2):252–271.
  * Bessiere et al. (2009) Bessiere C, Hebrard E, O’Sullivan B (2009) Minimising decision tree size as combinatorial optimisation. Gent IP, ed., _Principles and Practice of Constraint Programming - CP 2009_ , 173–187 (Berlin, Heidelberg: Springer Berlin Heidelberg).
  * Bixby (2012) Bixby R (2012) A brief history of linear and mixed-integer programming computation. _Documenta Mathematica_ 107–121.
  * Blanquero et al. (2021) Blanquero R, Carrizosa E, Molero-Río C, Morales DR (2021) Optimal randomized classification trees. _Computers & Operations Research_ 132:105281.
  * Boland et al. (2015) Boland N, Charkhgard H, Savelsbergh M (2015) A criterion space search algorithm for biobjective mixed integer programming: The triangle splitting method. _INFORMS Journal on Computing_ 27(4):597–618.
  * Breiman et al. (1984) Breiman L, Friedman J, Stone CJ, Olshen RA (1984) _Classification and regression trees_ (CRC press).
  * Buciu et al. (2006) Buciu I, Kotropoulos C, Pitas I (2006) Demonstrating the stability of support vector machines for classification. _Signal Processing_ 86:2364–2380.
  * Charlot and Marimoutou (2014) Charlot P, Marimoutou V (2014) On the relationship between the prices of oil and the precious metals: Revisiting with a multivariate regime-switching decision tree. _Energy Economics_ 44:456–467.
  * Dash et al. (2018) Dash S, Günlük O, Wei D (2018) Boolean decision rules via column generation. Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds., _Advances in Neural Information Processing Systems_ , volume 31 (Curran Associates, Inc.).
  * Delen et al. (2013) Delen D, Kuzey C, Uyar A (2013) Measuring firm performance using financial ratios: A decision tree approach. _Expert Systems with Applications_ 40(10):3970–3983.
  * Demirović et al. (2022) Demirović E, Lukina A, Hebrard E, Chan J, Bailey J, Leckie C, Ramamohanarao K, Stuckey P (2022) Murtree: Optimal decision trees via dynamic programming and search. _Journal of Machine Learning Research_ 23(26), ISSN 1532-4435.
  * Esmeir and Markovitch (2007) Esmeir S, Markovitch S (2007) Anytime learning of decision trees. _J. Mach. Learn. Res._ 8:891–933, ISSN 1532-4435.
  * Firat et al. (2020) Firat M, Crognier G, Gabor AF, Hurkens CA, Zhang Y (2020) Column generation based heuristic for learning classification trees. _Computers & Operations Research_ 116:104866.
  * Fischetti et al. (2017) Fischetti M, Leitner M, Ljubić I, Luipersbeck M, Monaci M, Resch M, Salvagnin D, Sinnl M (2017) Thinning out Steiner trees: a node-based model for uniform edge costs. _Mathematical Programming Computation_ 9(2):203–229.
  * Ford and Fulkerson (1962) Ford LR, Fulkerson DR (1962) _Flows in networks_ (Princeton University Press).
  * Fu et al. (2020) Fu R, Huang Y, Singh PV (2020) Artificial intelligence and algorithmic bias: Source, detection, mitigation, and implications. _INFORMS Tutorials in Operations Research_ 39–63.
  * Gini (1912) Gini C (1912) Variabilità e mutabilità. _Journal of the Royal Statistical Society_ 76:326–327.
  * Günlük et al. (2021) Günlük O, Kalagnanam J, Li M, Menickelly M, Scheinberg K (2021) Optimal decision trees for categorical data via integer programming. _Journal of Global Optimization_ 233–260.
  * Haber and Ruthotto (2017) Haber E, Ruthotto L (2017) Stable architectures for deep neural networks. _Inverse Problems_ 34(1):014004.
  * Hochbaum (2018) Hochbaum DS (2018) Machine learning and data mining with combinatorial optimization algorithms. _INFORMS Tutorials in Operations Research_ 109–129.
  * Hu et al. (2019) Hu X, Rudin C, Seltzer M (2019) Optimal sparse decision trees. Wallach H, Larochelle H, Beygelzimer A, d'Alché-Buc F, Fox E, Garnett R, eds., _Advances in Neural Information Processing Systems_ , volume 32 (Curran Associates, Inc.).
  * Huchette and Vielma (2019) Huchette J, Vielma JP (2019) A geometric way to build strong mixed-integer programming formulations. _Operations Research Letters_ 47(6):601–606, ISSN 0167-6377.
  * Hyafil and Rivest (1976) Hyafil L, Rivest RL (1976) Constructing optimal binary decision trees is np-complete. _Inf. Process. Lett._ 5(1):15–17.
  * Kaplan and Nussbaum (2011) Kaplan H, Nussbaum Y (2011) Minimum $s-t$ cut in undirected planar graphs when the source and the sink are close. _Symposium on Theoretical Aspects of Computer Science (STACS2011)_ , volume 9, 117–128 (Dortmund, Germany).
  * Kass (1980) Kass GV (1980) An exploratory technique for investigating large quantities of categorical data. _Journal of the Royal Statistical Society: Series C (Applied Statistics)_ 29(2):119–127.
  * Kim and Loh (2001) Kim H, Loh WY (2001) Classification trees with unbiased multiway splits. _Journal of the American Statistical Association_ 96:589–604.
  * Kontschieder et al. (2015) Kontschieder P, Fiterau M, Criminisi A, Bulò SR (2015) Deep neural decision forests. _2015 IEEE International Conference on Computer Vision (ICCV)_ , 1467–1475.
  * Kullback and Leibler (1951) Kullback S, Leibler RA (1951) On information and sufficiency. _Annals of Mathematical Statistics_ 22:79–86.
  * Kumar et al. (2013) Kumar A, Hanmandlu M, Gupta H (2013) Fuzzy binary decision tree for biometric based personal authentication. _Neurocomputing_ 99:87–97.
  * Land and Doig (1960) Land A, Doig A (1960) An automatic method of solving discrete programming problems. _Econometrica_ 28(3):497–520.
  * Lee and Jaakkola (2020) Lee G, Jaakkola TS (2020) Oblique decision trees from derivatives of relu networks. _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_ (OpenReview.net).
  * Leung et al. (2003) Leung F, Lam H, Ling S, Tam P (2003) Tuning of the structure and parameters of a neural network using an improved genetic algorithm. _IEEE Transactions on Neural Networks_ 14(1):79–88.
  * Li et al. (2021) Li Z, Wang L, Huang Ls, Zhang M, Cai X, Xu F, Wu F, Li H, Huang W, Zhou Q, et al. (2021) Efficient management strategy of covid-19 patients based on cluster analysis and clinical decision tree classification. _Scientific reports_ 11(1):1–13.
  * Loh and Shih (1997) Loh WY, Shih YS (1997) Split selection methods for classification trees. _Statistica sinica_ 815–840.
  * Magee (1964) Magee JF (1964) _Decision trees for decision making_ (Harvard Business Review).
  * Malik and Singh (2019) Malik N, Singh PV (2019) Deep learning in computer vision: Methods, interpretation, causation, and fairness. _INFORMS Tutorials in Operations Research_ 73–100.
  * Manogna and Mishra (2021) Manogna R, Mishra AK (2021) Measuring financial performance of indian manufacturing firms: application of decision tree algorithms. _Measuring Business Excellence_ .
  * Maturana et al. (2011) Maturana D, Mery D, Soto Á (2011) Face recognition with decision tree-based local binary patterns. _Computer Vision – ACCV 2010_ , 618–629 (Springer Berlin Heidelberg).
  * Mehta et al. (1996) Mehta M, Agrawal R, Rissanen J (1996) Sliq: A fast scalable classifier for data mining. _International conference on extending database technology_ , 18–32 (Springer).
  * Menze et al. (2011) Menze BM Bjoern Hand Kelm, Splitthoff DN, Koethe U, Hamprecht FA (2011) On oblique random forests. Gunopulos D, Hofmann T, Malerba D, Vazirgiannis M, eds., _Machine Learning and Knowledge Discovery in Databases_ , 453–469 (Berlin, Heidelberg: Springer Berlin Heidelberg).
  * Murthy (2004) Murthy SK (2004) Automatic construction of decision trees from data: A multi-disciplinary survey. _Data Mining and Knowledge Discovery_ 2:345–389.
  * Murthy et al. (1994) Murthy SK, Kasif S, Salzberg SL (1994) A system for induction of oblique decision trees. _J. Artif. Intell. Res._ 2:1–32.
  * Narodytska et al. (2018) Narodytska N, Ignatiev A, Pereira F, Marques-Silva J (2018) Learning optimal decision trees with sat. _Proceedings - 27th International Joint Conference on Artificial Intelligence, IJCAI 2018_ , 1362–1368 (United States of America: Association for the Advancement of Artificial Intelligence (AAAI)).
  * Nijssen and Fromont (2007) Nijssen S, Fromont E (2007) Mining optimal decision trees from itemset lattices. _Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , 530–539 (New York, NY, USA: Association for Computing Machinery).
  * Norton (1989) Norton SW (1989) Generating better decision trees. _Proceedings of the 11th International Joint Conference on Artificial Intelligence - Volume 1_ , 800–805, IJCAI’89 (San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.).
  * Orsenigo and Vercellis (2003) Orsenigo C, Vercellis C (2003) Multivariate classification trees based on minimum features discrete support vector machines. _Ima Journal of Management Mathematics_ 14:221–234.
  * Pereira et al. (2009) Pereira F, Norvig P, Halevy A (2009) The unreasonable effectiveness of data. _IEEE Intelligent Systems_ 24(02):8–12, ISSN 1941-1294.
  * Perini et al. (2020) Perini T, Boland N, Pecin D, Savelsbergh M (2020) A criterion space method for biobjective mixed integer programming: The boxed line method. _INFORMS Journal on Computing_ 32(1):16–39.
  * Quinlan (1986) Quinlan JR (1986) Induction of decision trees. _Mach. Learn._ 1(1):81–106.
  * Quinlan (1993) Quinlan JR (1993) _C4.5: Programs for Machine Learning_ (Morgan Kaufmann).
  * Ruiz et al. (2021) Ruiz L, Wang Z, Ribeiro A (2021) Graphon and graph neural network stability. _ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 5255–5259.
  * Shafer et al. (1996) Shafer J, Agrawal R, Mehta M (1996) Sprint: A scalable parallel classifier for data mining. _Vldb_ , volume 96, 544–555 (Citeseer).
  * Shannon (1948) Shannon C (1948) A mathematical theory of communication. _Bell System Technical Journal_ 27:379–423.
  * Steffy and Wolter (2013) Steffy DE, Wolter K (2013) Valid linear programming bounds for exact mixed-integer programming. _INFORMS Journal on Computing_ 25(2):271–284.
  * Valdivia et al. (2021) Valdivia A, Sánchez‐Monedero J, Casillas J (2021) How fair can we go in machine learning? assessing the boundaries of accuracy and fairness. _International Journal of Intelligent Systems_ 36(4):1619–1643, ISSN 1098-111X.
  * van der Blom et al. (2020) van der Blom K, Deist TM, Volz V, Marchi M, Nojima Y, Naujoks B, Oyama A, Tusar T (2020) Identifying properties of real-world optimisation problems through a questionnaire. _CoRR_ abs/2011.05547.
  * Verwer and Zhang (2019) Verwer S, Zhang Y (2019) Learning optimal classification trees using a binary linear program formulation. _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, 1625–1632.
  * Vielma (2015) Vielma JP (2015) Mixed integer linear programming formulation techniques. _SIAM Review_ 57(1):3–57.
  * Wang et al. (2015) Wang J, Fujimaki R, Motohashi Y (2015) Trading interpretability for accuracy: Oblique treed sparse additive models. _Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ .
  * Wickramarachchi et al. (2016) Wickramarachchi DC, Robertson BL, Reale M, Price CJ, Brown J (2016) Hhcart: An oblique decision tree. _Comput. Stat. Data Anal._ 96:12–23.
  * Witzig and Gleixner (2021) Witzig J, Gleixner A (2021) Conflict-driven heuristics for mixed integer programming. _INFORMS Journal on Computing_ 33(2):706–720.
  * Yang et al. (2018) Yang Y, Morillo IG, Hospedales TM (2018) Deep neural decision trees. _CoRR_ abs/1806.06988.
  * Yoo et al. (2020) Yoo SH, Geng H, Chiu TL, Yu SK, Cho DC, Heo J, Choi MS, Choi IH, Cung Van C, Nhung NV, Min BJ, Lee H (2020) Deep learning-based decision-tree classifier for covid-19 diagnosis from chest x-ray imaging. _Frontiers in Medicine_ 7\.
  * Zantedeschi et al. (2020) Zantedeschi V, Kusner MJ, Niculae V (2020) Learning binary trees via sparse relaxation. _ArXiv_ abs/2010.04627.
  * Zhang and Ntoutsi (2019) Zhang W, Ntoutsi E (2019) FAHT: an adaptive fairness-aware decision tree classifier. _CoRR_ abs/1907.07237.
  * Zhen et al. (2022) Zhen J, de Ruiter FJCT, Roos E, den Hertog D (2022) Robust optimization for models with uncertain second-order cone and semidefinite programming constraints. _INFORMS Journal on Computing_ 34(1):196–210.
  * Zhu et al. (2020) Zhu H, Murali P, Phan DT, Nguyen LM, Kalagnanam JR (2020) A scalable MIP-based method for learning optimal multivariate decision trees. _Advances in Neural Information Processing Systems_ 33\.

## 8

Table 5: Average in-sample accuracy (%). Best in bold (* if $\operatorname{BendersOCT}$ performed best). Dataset | $D_{h}$ | FlowOCT | $\operatorname{MCF1}$ | $\operatorname{MCF2}$ | $\operatorname{CUT1}$ | $\operatorname{CUT2}$ | $\operatorname{BendersOCT}$
---|---|---|---|---|---|---|---
soybean-small | 2 | 100 | 100 | 100 | 100 | 100 | 100*
3 | 100 | 100 | 100 | 100 | 100 | 100*
4 | 100 | 100 | 100 | 100 | 100 | 100*
5 | 100 | 100 | 100 | 100 | 100 | 100*
monk3 | 2 | 93.77 | 93.19 | 93.19 | 93.19 | 93.19 | 93.77*
3 | 95.74 | 95.38 | 95.38 | 95.38 | 95.38 | 96.07*
4 | 98.03 | 98.46 | 98.68 | 98.68 | 98.68 | 99.02*
5 | 100 | 100 | 100 | 100 | 100 | 100*
monk1 | 2 | 82.26 | 81.51 | 81.51 | 81.51 | 81.51 | 82.26*
3 | 91.29 | 92.04 | 92.04 | 92.04 | 92.04 | 90.97
4 | 100 | 100 | 100 | 100 | 100 | 100*
5 | 100 | 100 | 100 | 100 | 100 | 100*
hayes-roth | 2 | 64.55 | 65.25 | 65.25 | 65.25 | 65.25 | 64.24
3 | 80.00 | 79.60 | 79.60 | 79.60 | 79.60 | 80.00*
4 | 90.00 | 88.89 | 88.89 | 88.89 | 88.89 | 89.09
5 | 92.12 | 91.31 | 91.11 | 91.31 | 90.71 | 92.42*
monk2 | 2 | 67.62 | 68.25 | 68.25 | 68.25 | 68.25 | 67.62
3 | 76.67 | 77.14 | 77.14 | 77.30 | 77.30 | 75.71
4 | 81.43 | 83.17 | 83.02 | 83.49 | 83.17 | 82.38
5 | 90.00 | 91.59 | 90.16 | 91.47 | 92.46 | 90.71
house-votes-84 | 2 | 96.72 | 97.24 | 97.24 | 97.24 | 97.24 | 96.72
3 | 97.93 | 98.39 | 98.39 | 98.39 | 98.39 | 97.93
4 | 99.31 | 99.66 | 99.66 | 99.66 | 99.66 | 99.31
5 | 100 | 100 | 100 | 100 | 100 | 100*
spect | 2 | 79.85 | 79.80 | 79.80 | 79.80 | 79.80 | 79.85*
3 | 82.56 | 82.50 | 82.50 | 82.50 | 82.50 | 83.61*
4 | 88.12 | 87.00 | 87.00 | 87.10 | 87.10 | 88.12*
5 | 90.98 | 91.20 | 89.90 | 90.60 | 91.30 | 91.28
breast-cancer | 2 | 78.70 | 78.45 | 78.45 | 78.45 | 78.45 | 78.99*
3 | 83.91 | 81.84 | 81.74 | 82.32 | 82.42 | 83.04
4 | 87.20 | 85.35 | 86.80 | 86.47 | 86.63 | 87.10
5 | 90.22 | 89.86 | 89.37 | 90.82 | 89.86 | 91.74*
balance-scale | 2 | 69.04 | 69.49 | 69.49 | 69.49 | 69.49 | 69.17
3 | 75.06 | 75.77 | 75.77 | 75.77 | 75.77 | 75.13
4 | 78.85 | 79.10 | 78.76 | 78.97 | 78.97 | 78.53
5 | 81.47 | 82.35 | 82.56 | 82.44 | 82.26 | 82.24
tic-tac-toe | 2 | 70.90 | 70.97 | 70.97 | 70.97 | 70.97 | 70.77
3 | 77.83 | 76.46 | 77.52 | 77.86 | 77.33 | 77.62
4 | 84.38 | 81.92 | 83.70 | 83.90 | 83.54 | 83.55
5 | 86.76 | 88.52 | 88.66 | 86.10 | 87.16 | 88.10
car_evaluation | 2 | 77.43 | 77.78 | 77.78 | 77.78 | 77.78 | 77.43
3 | 80.81 | 80.23 | 80.97 | 81.23 | 81.22 | 80.81
4 | 82.55 | 78.18 | 82.35 | 81.54 | 82.05 | 82.59
5 | 83.84 | 72.35 | 75.91 | 71.82 | 74.58 | 84.58*
kr-vs-kp | 2 | 87.31 | 86.97 | 86.97 | 86.97 | 86.97 | 87.31*
3 | 84.91 | 72.50 | 78.87 | 86.78 | 84.85 | 92.33*
4 | 78.25 | 52.22 | 64.10 | 68.54 | 70.10 | 89.11*
5 | 79.84 | 64.07 | 68.58 | 74.70 | 70.16 | 95.16*
fico_binary | 2 | 71.22 | 71.19 | 71.27 | 71.27 | 71.27 | 71.22
3 | 71.59 | 71.44 | 71.45 | 70.48 | 70.51 | 70.97
4 | 70.89 | 52.96 | 62.38 | 52.96 | 52.96 | 70.64
5 | 69.65 | 52.96 | 61.93 | 52.96 | 52.96 | 71.11*
Table 6: Average solution time. Best in bold (* if $\operatorname{BendersOCT}$ performed best). Dataset | $D_{h}$ | FlowOCT | $\operatorname{MCF1}$ | $\operatorname{MCF2}$ | $\operatorname{CUT1}$ | $\operatorname{CUT2}$ | $\operatorname{BendersOCT}$
---|---|---|---|---|---|---|---
soybean-small | 2 | 0.08 | 0.10 | 0.06 | 0.04 | 0.07 | 0.20
3 | 0.16 | 0.08 | 0.09 | 0.08 | 0.08 | 0.20
4 | 0.33 | 0.28 | 0.27 | 0.22 | 0.22 | 0.36
5 | 0.65 | 0.52 | 0.65 | 0.49 | 0.50 | 0.49
monk3 | 2 | 0.51 | 0.94 | 1.02 | 0.56 | 0.56 | 0.23*
3 | 91.98 | 105.15 | 92.57 | 66.25 | 91.99 | 15.70*
4 | 2210.76 | 2186.47 | 2197.56 | 1733.84 | 1924.94 | 2381.33
5 | 187.22 | 219.00 | 142.03 | 79.16 | 136.59 | 42.62
monk1 | 2 | 0.74 | 1.68 | 1.12 | 0.67 | 0.73 | 0.48*
3 | 32.65 | 35.65 | 35.19 | 25.44 | 25.73 | 4.33
4 | 15.89 | 22.63 | 8.92 | 9.87 | 13.01 | 2.13
5 | 8.46 | 16.60 | 13.78 | 12.06 | 12.52 | 1.51
hayes-roth | 2 | 0.69 | 2.69 | 1.01 | 0.62 | 0.62 | 0.83
3 | 13.86 | 59.02 | 31.50 | 40.76 | 26.83 | 7.86*
4 | 2430.02 | 1819.18 | 1415.03 | 1512.81 | 1270.11 | 2422.33
5 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00*
monk2 | 2 | 6.76 | 5.83 | 3.40 | 1.87 | 1.92 | 3.12
3 | 2935.01 | 1898.05 | 469.60 | 1014.42 | 804.51 | 1205.76
4 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00*
5 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00*
house-votes-84 | 2 | 0.76 | 2.97 | 1.97 | 1.06 | 1.07 | 0.48
3 | 200.91 | 167.30 | 127.05 | 173.64 | 133.14 | 80.30*
4 | 2882.22 | 2169.07 | 1087.32 | 1144.08 | 1209.22 | 2882.02
5 | 471.55 | 62.14 | 76.84 | 115.90 | 116.20 | 555.25
spect | 2 | 9.97 | 15.90 | 13.96 | 2.84 | 2.63 | 4.14
3 | 2790.05 | 1760.49 | 1736.55 | 942.73 | 1385.65 | 2162.11
4 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00*
5 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00*
breast-cancer | 2 | 23.69 | 45.94 | 7.79 | 7.68 | 7.43 | 17.19
3 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00*
4 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00*
5 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00*
balance-scale | 2 | 10.51 | 21.68 | 17.16 | 7.29 | 7.23 | 6.60*
3 | 1863.60 | 1651.92 | 1384.10 | 1235.88 | 1232.90 | 895.25*
4 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00*
5 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00*
tic-tac-toe | 2 | 490.04 | 327.18 | 96.10 | 93.31 | 104.08 | 139.20
3 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00*
4 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00*
5 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00*
car_evaluation | 2 | 83.46 | 111.03 | 45.28 | 38.99 | 35.97 | 32.08*
3 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00*
4 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00*
5 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00*
kr-vs-kp | 2 | 598.99 | 3155.29 | 1029.96 | 1188.90 | 1199.33 | 420.01*
3 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00*
4 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00*
5 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00*
fico_binary | 2 | 944.53 | 3600.00 | 858.20 | 955.18 | 1408.68 | 2414.30
3 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00*
4 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00*
5 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00 | 3600.00*
Table 7: Average in-sample optimality gap (%). Best in bold (* if $\operatorname{BendersOCT}$ performed best). Dataset | $D_{h}$ | FlowOCT | $\operatorname{MCF1}$ | $\operatorname{MCF2}$ | $\operatorname{CUT1}$ | $\operatorname{CUT2}$ | $\operatorname{BendersOCT}$
---|---|---|---|---|---|---|---
soybean-small | 2 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00*
3 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00*
4 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00*
5 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00*
monk3 | 2 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00*
3 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00*
4 | 1.81 | 1.35 | 0.67 | 0.00 | 0.22 | 1.35
5 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00*
monk1 | 2 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00*
3 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00*
4 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00*
5 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00*
hayes-roth | 2 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00*
3 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00*
4 | 4.90 | 0.00 | 0.00 | 0.00 | 0.00 | 0.46
5 | 8.86 | 9.53 | 8.66 | 9.12 | 9.82 | 9.06
monk2 | 2 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00*
3 | 2.54 | 0.85 | 0.85 | 0.00 | 0.00 | 0.00*
4 | 17.23 | 18.36 | 17.43 | 18.05 | 18.60 | 12.95*
5 | 11.71 | 9.20 | 8.48 | 9.20 | 8.45 | 10.38
house-votes-84 | 2 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00*
3 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.01
4 | 80.00 | 0.23 | 0.00 | 0.00 | 0.12 | 0.46
5 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00*