Noname manuscript No.

(will be inserted by the editor)

Learning Optimal Decision Trees using Constraint
Programming
Hélène Verhaeghe · Siegfried Nijssen · Gilles
Pesant · Claude-Guy Quimper · Pierre
Schausthe date of receipt and acceptance should be inserted later

Abstract Decision trees are among the most popular classification models in ma-chine learning. Traditionally, they are learned using greedy algorithms. However,such algorithms pose several disadvantages: it is difficult to limit the size of thedecision trees while maintaining a good classification accuracy, and it is hard to
impose additional constraints on the models that are learned. For these reasons,
there has been a recent interest in exact and flexible algorithms for learning decision trees. In this paper, we introduce a new approach to learn decision trees
using constraint programming. Compared to earlier approaches, we show that ourapproach obtains better performance, while still being sufficiently flexible to allow
for the inclusion of constraints. Our approach builds on three key building blocks:(1) the use of AND/OR search, (2) the use of caching, (3) the use of the CoverSize
global constraint proposed recently for the problem of itemset mining. This allows
our constraint programming approach to deal in a much more efficient way withthe decompositions in the learning problem.
Keywords Decision Tree, CoverSize, AND/OR search tree, Caching

1 Introduction

Decision trees are popular classification models in machine learning. Benefits ofdecision trees include that they are relatively easy to interpret and that they
provide good classification performance on many datasets.
Several methods have been proposed in the literature for learning decision
trees. The greedy methods are the most popular ones [6, 19, 20]. These methods
H. Verhaeghe, S. Nijssen and P. Schaus
UCLouvain, ICTEAM, Place Sainte Barbe 2, 1348 Louvain-la-Neuve, Belgium, E-mail:{firstname.lastname}@uclouvain.be
G.Pesant
Polytechnique Montréal, Montréal, Canada, E-mail: gilles.pesant@polymtl.ca
C.-G. Quimper
Université Laval, Québec, Canada, E-mail: claude-guy.quimper@ift.ulaval.ca

2Hélène Verhaeghe et al.

recursively partition a dataset into two subsets based on a greedily selected attribute until some stopping criterion is reached (such as a minimum number ofexamples in the leaf, or a unique class label in these examples). While in practicethese methods obtain a good prediction accuracy for many types of data, unfortunately, they provide little guarantees. As a result, the trees learned using thesemethods may be unnecessarily complex, may be less accurate than possible, and
it is hard to impose additional constraints on the trees, such as on the fairness of
their predictions.
To address these weaknesses, researchers have studied the inference of optimal
decision trees under constraints [1, 3, 4, 15–17, 26]1 . These approaches ensure that
under well-defined constraints and optimization criteria, an optimal tree is found.
Experiments conducted in earlier work [3, 16, 17] have shown that optimal decision
trees computed with these exact methods can indeed obtain better classification
performance while respecting constraints.
A problem that is solved by many of these earlier approaches [3, 16, 17, 26]
is the following. Given a dataset in which all examples are binary; the problem
is to find the decision tree that optimizes prediction accuracy, while enforcing a
constraint on the depth of the decision tree.
The key ideas behind this constraint are that it limits the complexity of thedecision tree, hence making the predictions of the tree easier to interpret while
preventing over-fitting.
Several papers have studied the addition of other constraints to these approaches, including support constraints on the leaves of the tree [3, 17], on fairness[1], or on the preservation of privacy by these trees [17].
We suspect, as papers [3, 17, 26], that the problem of finding an optimal decision
tree given a maximum depth is NP-complete even if no formal proof is available
yet. Clearly the problem is in NP. As the depth is bounded, at most d tests are
required to classify one of the transactions from the database. Therefore, the error
can be computed in O(nd) (with n the total number of transactions and d the
maximum depth), which is polynomial. Similar problems have been proven NPComplete. Hyafil and Rivest [12] found that the problem of finding a decision tree
which minimizes the expected number of tests to classify a new transaction is NPcomplete. The problem of finding a decision tree minimizing the number of leaves
is also proven NP-complete in [11].
Hence, approaches for this problem need to perform some form of exhaustive
search through the space of possible trees. To explore this search space, earlier
approaches have been built on existing technologies: Mixed Integer Programming(MIP) solvers, satisfiability (SAT) solvers, or itemset mining algorithms developedin the data mining literature.
This paper proposes a new, more scalable approach based on Constraint Programming (CP) for learning decision trees. Our approach combines these key ideas:– the use of branch-and-bound in a CP solver to eliminate parts of the search

space in which no solutions can be found;– the use of the CoverSize global constraint, originally developed for itemset

mining in CP, to calculate efficiently in which leaf examples end up [23];1 The problem of embedding a decision tree as a constraint into a CP model has been studied
in [5].

Learning Optimal Decision Trees using Constraint Programming3– the use of an AND/OR search tree to exploit the fact that the optimal left-handand right-hand subtrees of a node in a decision tree can be found independently
from each other [8];– the use of caching to store optimal decision trees for itemsets that have been
considered in the past [16].
We will show that the combination of these different ideas leads to a model thatis more efficient than other approaches proposed in the literature.
The paper is organized as follows. Section 2 presents the state of the art,
followed by a formal definition of the problem in Section 3. Our CP model and
CP search are detailed in Section 5. Finally, Section 6 presents empirical results
about our algorithm.

2 Related Work

Most related to this work are the alternative approaches for finding optimal decision trees. There is a number of alternative definitions for the problem of finding
optimal decision trees, each using different constraints and optimization criteria.
The most popular setting studied in recent papers [1, 3, 26] is the one in whicha decision tree of bounded depth is learned by maximizing the accuracy on a given
training dataset. The limit on depth allows to model the problem as a MIP problem
with a fixed number of variables. Constraints can be added, as long as they arelinear; this includes constraints on fairness [1] or on the number of examples in
the leafs [3]. We will use this problem setting in this work.
A slightly different setting was studied in the DL8 algorithm [17]. DL8 builds
on top of itemset mining algorithms to find decision tree paths, and uses dynamic
programming to build a decision tree from these paths. Effectively, it uses itemsets
as the key of a caching data structure. As a consequence of the use of itemset
mining, DL8 does not require a specific constraint on the depth of the decision
tree; it uses a minimum support constraint to limit the size of the search space.
This approach can be used on constraints that are not linear in nature. From thisapproach, we will adapt its link to itemset mining, and its use of caching.
To the best of our knowledge, CP has not yet been used in the setting whereaccuracy is optimized. Two earlier studies [4, 15] did, however, study the settingin which one finds the smallest decision tree consistent with a training dataset(i.e. the error of the decision tree has to be zero). As training data can be noisy
and inconsistent, and hence finding a tree of zero error can be either impossibleor undesirable, this setting is less common in the machine learning literature.
Similar to DL8, we will rely in this work on the fact that decision tree learning
problems have many decompositions. We will exploit these using AND/OR search,which was studied extensively by Dechter et al. [8]. AND/OR search is not common
in CP systems yet, and has not been used in decision tree learning yet; it has
recently been exploited in the context of stochastic CP however [2].

4Hélène Verhaeghe et al.

3 Technical Background

3.1 Definition of the Problem
We restrict our attention to binary data. Continuous data can be discretized andbinarized as proposed by Breiman et al. [6]; this observation was also exploited inearlier studies [16, 26].
We represent our data using an n × m binary matrix D. Di represents the ith
row of the data, or, following itemset mining terminology, the ith transaction of D.
The number of transactions is thus n. The columns of the matrix represent the mfeatures or items of the transactions. Di,j represents the value of the j th feature of
Di , i.e., 0 or 1 as we work with binary features. We assume in this work that eachtransaction belongs to one of two classes, represented by 0 and 1. The classes are
stored in a vector v of size n. Hence, the database can be split into D+ , a matrixof size n+ × m, containing all the transactions from D associated to class 1, andD− , a matrix of size n− × m, containing the ones associated to class 0.
In this work we are interested in finding decision trees. Each internal node w
of a decision tree is associated to a feature (called the decision of the node) d[w] ∈{1, . . . , m}; each leaf is associated to a Boolean b[w], representing the prediction
for that leaf. We will use the function F (r, t) to represent the predicted value fortransaction t on a tree with root r, defined recursively as
if w is a leaf; b[w](1)
F (w, t) = F (left(w), t) if Dt,d[w] = 1;
F (right(w), t) if Dt,d[w] = 0.
Here left(w) (resp. right(w)) returns the left-hand (resp. right-hand) subtree of
node w.
We focus on creating well-formed decision trees. This means that a given feature can be used at most once on each path from the root to a leaf. Also, each
subtree rooted in one of the inner nodes should not have all its leaves assigned tothe same class.
We define the depth d of a decision tree to be the maximum number of featureson any path from the root of the tree towards a leaf. Given a maximum depth,
our goal is to find a decision tree that minimizes the number of misclassified
transactions (i.e. transactions where the class of the transaction, v [t], is different
from the classification by the tree, F (r, t)):
min

n
X

[F (r, t) 6= v [t]].

(2)

t=1

We allow for the additional specification of a constraint on the minimum numberof examples Nmin in each leaf of the tree [3, 17],
An extension of the problem is to consider more than two classes (multi-classdecision trees). We will limit our discussion to binary classes, but the extension
towards data with more than two classes is relatively straightforward.
Let us give a simple example. Given the dataset in Fig. 1a, a possible decision
tree of depth 2 is provided in Fig. 1b. For patient 1, the tree predicts the correctclass (she does not have a cough and does not smoke, which leads to the fourthleaf, which categorizes the patient as sick). For patient 4, the tree produces aLearning Optimal Decision Trees using Constraint Programming

Patient 1
Patient 2
Patient 3
Patient 4..
.

5

Fever?

Cough?

Age > 60?

Smoke?

...

Sick from A?

3
3
8
8
..
.

8
3
8
3
..
.

3
8
3
3
..
.

8
8
3
3
..
.

...
...
...
...
..
.

3
3
8
3
..
.

(a) Dataset
Cough?

yesno

Fever?

Sick


Sick


Smoke?


Sick


Sick

(b) Decision tree

Fig. 1: Example

faulty classification (she has a cough and does not have a fever, which leads tothe second leaf and categorizes the patient as not sick). The tree is the optimal
decision tree of maximum depth 2 with respect to the classification error if thenumber of misclassified patients is the smallest among all the possible trees ofmaximum depth 2.

3.2 Constraint Programming
Constraint programming (CP) [21] is a computational paradigm aiming at solving combinatorial problems (satisfaction and optimization ones). The problem isstated as a set of variables and a set of constraints acting on the variables. The
constraints represent the properties that should be respected in a solution (i.e. anassignment of a value to each variable). An example of a constraint is the AllDifferent constraint. It specifies that each variable involved should take a different value
in a valid assignment. The variables and constraints form the model of the problem. A search tree is then explored (usually using backtracking depth first search)
to discover an assignment of all the variables that satisfies all the constraints. A
heuristic decides at each node of the search tree which variable and value should
be assigned/removed in the next two alternative branches. For example, a first
fail heuristic selects, at each node of the search tree, the unbound variable withthe smallest remaining domain. The search tree is pruned by the constraints incharge of removing infeasible values from the domain of the variables during the
fix-point computation triggered at each node of the search tree. A backtrack occurs when one domain becomes empty. We refer to [13] for more information about
Constraint Programming technology.

6Hélène Verhaeghe et al.

3.3 AND/OR Search Trees
In a classical CP framework, the search tree is only composed of OR nodes. Eachbranch starting at an OR node adds a simple constraint in order to cut the search
space. To keep the search complete, the branches should be complementary andtogether still represent the full search space. The optimal solution lies in one of the
branches. An example could be to branch using x = v and x 6= v . The first branch
restricts the domain of x to the singleton {v}, while the other branch restricts it
to dom(x)\{v}. The union of the two branches covers all the possible values of x.
Another example could be to create a branch for each of the values of the domainof a given variable, each assigning this value to the variable.
In AND/OR search trees [9, 14], a second type of node is introduced: the AND
nodes. Each branch starting at an AND node represents a distinct, independent
subproblem. The set of unbound variables and the set of remaining constraints are
partitioned into disjoint sets. The solution, if it exists, is therefore the conjunctionof the partial solutions of all the branches. If one branch does not have a solution,then no solution exists for the node. An example: given a problem of 5 variables(dom(A) = {5}, dom(B1 ) = dom(B2 ) = dom(C1 ) = dom(C2 ) = {0, 1, 2, 3, 4, 5}) andtwo constraints (A = B1 + C1 and A = B2 + C2 ), since A is bound, the problem
can be partitioned into two independent subproblems. On the first branch, B1 , C1
and A = B1 + C1 form the first sub-problem, while B2 , C2 and A = B2 + C2 forms
the second, on the second branch.
An AND/OR search tree combines both OR and AND nodes in order to findsolutions to the problem.
3.4 The CoverSize Constraint
To determine the accuracy of a decision tree, we need to decide in which nodes ofthe decision tree a transaction ends up. A correspondence can be drawn here withthe cover of itemsets in itemset mining [16, 17]. We exploit this correspondence byadapting the CoverSize global constraint [23] to the context of learning decision
trees. The original CoverSize has the following parameters: an array of Boolean
variables (one variable for each feature), the database, and a counter variable, andis defined as follows:
CoverSize([I1 , . . . , Im ], D, c) ⇐⇒ c =\{t ∈ {1, . . . , n} | Dt,i = 1} .

(3)

Ii =1

The goal of the constraint is to link an itemset to the number of transactions containing the itemset. The itemset is represented by the Boolean array [I1 , . . . , Im ]:Boolean Ii is true if and only if feature i is included in the itemset. A transaction
contains an itemset if and only if every feature in the itemset has value 1 in thetransaction. The algorithm described in [23] is bound consistent.
For example, reusing the dataset in Fig. 1a, each Boolean is linked to oneof the features (Fever?, Cough?,...). Given the selected features (i.e. corresponding Boolean set to true) forming the pattern, the constraint ensures that thecounter corresponds to how many transactions matches this pattern. If the only
true Boolean are IFever? and IAge>60? , then on the displayed patients, only the
first should be counted, since she is the only one to have both features.

Learning Optimal Decision Trees using Constraint Programming

7

4 Preliminaries: Adaptation of CoverSize

The CoverSize constraint, in its original form, does not suit our application rightaway. Our aim is to use it to link the number of transactions matching a given
series of decisions (i.e. the path to the corresponding leaf). Given a tree, we know
two things about each series of decisions leading to a leaf. One, there is a fixed
number of decisions along the path and second, some are also rejecting decisions.
This led to the modifications made to the CoverSize propagation algorithm.
The dense representation of an itemset using a bit vector is unnecessary andimpractical in our application. Instead, we will use a sparse representation:
CoverSizeS({K1 , ..., Ka }, D, c) ⇐⇒ c =a\{t ∈ {1, ..., n} | Dt,Ki = 1}

(4)

i=1

This constraint has the following parameters: a set of integer variables {K1 , ..., Ka }(each representing the identifier of a selected feature), the database and the cover
counter. Similar propagation is possible for this constraint as for CoverSize.
Reusing the example in Fig. 1a and a pattern of size 2, if the two values assigned
to the variables are Fever? and Age>60?, then the constraint should ensure that
only patient 1 is counted (from the four displayed).
Note that in the standard CoverSize constraint, we only test whether an item
is included in a transaction (Dt,Ki = 1). In decision trees, we will also need to
be able to test that an item is absent in a transaction. Neither with the initial
CoverSize constraint nor its sparse version, is it possible to test for the absenceof an item. To address this weakness, we propose the CoverSizeSR constraint,
defined as follows:
CoverSizeSR({K1 , ..., Ka }, {L1 , ..., Lb }, D, c) ⇐⇒

|
c=

a
\

{z

take set} |{zdrop set}!

{t ∈ {1, ..., n} | Dt,Ki = 1}

i=1

\

b
\

!
{t ∈ {1, ..., n} | Dt,Li = 0}

(5)

i=1

The take (resp. drop ) set defines the features that should (resp. should not) appear
in the counted transactions.
Reusing the dataset in Fig. 1a, with a pattern consisting of two features, one
in the take set and one in the drop set, if their values are respectively Cough? andFever?, then only patient 4 (over the one displayed) matches the pattern and istherefore counted. In the decision tree of Fig. 1b, this pattern corresponds to thesecond leaf.
The pseudo-code of the CoverSizeSR propagator is given as Algorithm 1. Algorithm 2 details two methods used by the propagator. The key element of thealgorithm is the cover. It represents the set of transactions corresponding to thefeatures already selected in the take and drop sets. As in the original implementation of CoverSize, the cover is implemented using a reversible sparse bitset[10]. In this auto-backtracking structure, each bit is associated with one of thetransactions of the database. If the transaction is still valid concerning the alreadyselected features, then its associated bit is set to 1. It is set to 0 otherwise. To

8Hélène Verhaeghe et al.

help the computations, immutable bitsets are precomputed for each of the possible features. Each of these bitsets maintains the set of transactions containing the
given feature.

Algorithm 1: PropagateCoverSizeSR
take: Set of variables// set of take variable
drop: Set of variables// set of drop variable
3 c: Variable// counter variable
4 cover: Reversible Sparse Bitset// current cover
5 sizeCover: Integer// size of current cover
6 support: Array of Bitset// precomputed bitsets
7 Function propagate(take, drop, c, cover, sizeCover, support)
8
vars = take ∪ drop
9
takeU nbound ← { x | x ∈S take ∧ |dom(x)| > 1 }10remainingT akeV als ← x∈takeU nbound dom(x)11dropU nbound ← { x | x ∈S drop ∧ |dom(x)| > 1 }12remainingDropV als ← x∈dropU nbound dom(x)13isCoverChanged ← updateCover(take, drop, cover, sizeCover, support)// method defined at Algo.2
14c.max ← min(sizeCover, c.max)
15
if { x | x ∈ vars ∧ |dom(x)| > 1 } = ∅ then16c.min ← sizeCover
17
else
18
filterValues(remainingTakeVals, takeUnbound, remainingDropVals,
dropUnbound, c, cover, support)// method defined at Algo.2/* compute cover as if every decision available for the take set wereselected in the cover and every decision available for the drop
set were rejected from the cover*/19
if isCoverChanged ∧ ( remainingT akeV als ∩ remainingDropV als = ∅ )then20virtualCover ← cover21
foreach i ∈ remainingT akeV als do
22
virtualCover ← virtualCover ∩ support[i]
1

2

23
24
25
26

27
28
29
30
31

32
33
34
35

foreach i ∈ remainingDropV als do
virtualCover ← virtualCover ∩ support[i]Clb ← | virtualCover |c.min ← max(lb, c.min)/* if the counter variable is bounded to the current size of thecover, remove all values that would reduce the size of the cover*/
if |dom(c)| = 1 ∧ c.min = sizeCover thenforeach i ∈ remainingT akeV als do
if cover ∩ support[i] 6= cover thenforeach x ∈ takeU nbound dodom(x) ← dom(x)\{i}foreach i ∈ remainingDropV als do
if cover ∩ support[i]C 6= cover thenforeach x ∈ dropU nbound dodom(x) ← dom(x)\{i}Learning Optimal Decision Trees using Constraint Programming

9

Algorithm 2: PropagateCoverSizeSR: functions updateCover andfilterValues
Function updateCover(take, drop, cover, sizeCover, support)
mask ← cover/* Update cover with the new values chosen in the take set
3
foreach x ∈ take do
4
if x newly bound then // bound since last propagation5
mask ← mask ∩ support[x.value]
1
2

6
7
8
9
10
11
12
13
14

/* Update cover with the new values rejected in the drop set
foreach x ∈ drop do
if x newly bound then // bound since last propagation
mask ← mask ∩ support[x.value]C
if cover 6= mask thencover ← mask
sizeCover ← |cover|return true
else
return false*/*/// cover upper boundFunction filterValues(remainingTakeVals, takeUnbound, remainingDropVals,
dropUnbound, c, cover, support)/* Test remaining values available for the take set
16
foreach i ∈ remainingT akeV als do
17
count ← | cover ∩ support[i] |18
if count < c.min then // too few left to select19
foreach x ∈ takeU nbound do20
dom(x) ← dom(x)\{i}
15

21

22
23
24
25
26
27

*/

remainingT akeV als ← remainingT akeV als\{i}/* Test remaining values available for the drop set
foreach i ∈ remainingDropV als do // Remove impossible values
count ← | cover ∩ support[i]C |if count < c.min then // too few left to reject
foreach x ∈ dropU nbound dodom(x) ← dom(x)\{i}*/remainingDropV als ← remainingDropV als\{i}The algorithm first updates the cover (Algo.2 line 1) for each of the variables
newly bound. For each variable from the take set (Algo.2 line 3), the current coveris intersected with the support of the feature. For each variable from the dropset (Algo.2 line 6), the current cover is intersected with the complement of the
support of the feature. An updated cover allows to compute the new value of theupper bound of the counter.
If all the variables from both take and drop sets have been assigned, then the
cover cannot evolve (Algo.1 line 15). The previously computed upper bound is also
the lower bound. Otherwise, the computation continues.
Then, some features may be now impossible to select or reject and should be
filtered out of the domains (Algo. 2 line 15). This is triggered by a change in the
cover or a change in the domain of the counter. To test this, a virtual inclusion(resp. rejection) of the feature is done (Algo. 2 line 17 (resp. line 23)) by doing theintersection between the cover and the concerned support (resp. the complement of

10Hélène Verhaeghe et al.

the concerned support). This intersection corresponds to the number of remaining
transactions with (resp. without) the feature. Using the size of this intersection, we
can easily prevent the feature from being used in the take (resp. drop) set. If thesize is smaller than the current minimum, then the feature cannot be assigned toa take (resp. drop) set variable, i.e. not enough transactions with (resp. without)the feature to meet the current lower bound of the counter.
The next step is to compute a new lower bound (Algo. 1 line 19). This is done
by virtually selecting all the remaining values from both take and drop set into thecover. All the supports of the available values for the take set are intersected withthe cover and the complement of the supports of the available values for the drop
set are intersected. The size of this virtual cover is the smallest cover possible.
However, if a given value is still allowed in both the take and drop set, by theproperty stating that the intersection of a set and its complement is always empty,
the virtual cover is empty and the lower bound is equal to 0. The computation of
the lower bound can thus be avoided in such cases.
Finally, if the counter ends up taking the value of the size of the cover, thefeatures which modify the cover, and thus its size, should be removed from thedomains (Algo. 1 line 27).
n
) with w the size of the comThe time complexity of CoverSizeSR is O(m wputer words (e.g., w = 64). This is the same complexity as the CoverSize propan
gator. The space complexity is O(m w). The consistancy remains the same: boundconsistent.

5 CP Modeling of the Problem

5.1 Model of the Problem
In this section, we will introduce the variables and constraints used in our model.
Fig. 2 shows a visualization of our model for trees of a maximum depth of 3.
Note that in our model, we assume that a decision tree is a perfect tree. This
assumption is motivated by the existence of a mapping of any proper binary tree(i.e. a tree where each node has exactly 0 or 2 children) into a perfect one (i.e.
proper binary tree with all the leaves at the same level). We add a dummy feature
f0 , not belonging to any of the transactions, to the model for unused decision nodes.
Unlike other features used at most once per path, this feature is allowed multiple
times to allow any tree shape. A node with this value therefore has no transactions
from the database on its left branch. This assumption is also motivated by the CP
framework. Each potentially used variable should be defined before the start ofthe search. Figure 3 shows how a proper tree can be made perfect by the use of
the dummy feature.
The nodes (N ) of a perfect decision tree can be partitioned into two groups: thedecision nodes (N D ), which are associated to a decision and which have children,and the leaves (N L ), which do not have children. The decision nodes (N D ) can befurther partitioned into the end-nodes N E , which do not have decision nodes aschildren, and the nodes N N , which do. Variables and constraints are defined by
the type of the node.
In our model, the number of variables and constraints are independent fromthe number of transactions in the database and the number of features. In fact,

Learning Optimal Decision Trees using Constraint Programming

11

d[0]?

yes
no

NN
d[1]?

d[3]?

7

d[4]?

8

ND

d[2]?

9

d[5]?

10

NE

d[6]?

11

12

13

NL

14

Fig. 2: Representation of a perfect decision tree of depth 3
yes

f2 ?

f2 ?

no

f3 ?

f3 ?

f5 ?

+

f1 ?

+

-

f0 ?

-

+

f5 ?

/

f1 ?
+

+

f0 ?
-

/

f0 ?
+

/

-

(b) Equivalent perfect binary tree(a) Proper binary tree

Fig. 3: Example of the use of the dummy feature f0 to transform the proper binary
tree into a perfect binary tree

the number of variables and constraints only depends on the number of nodes inthe tree.
5.1.1 Variables

In our model we have variables with the following domains:dom(d[i]) = {0, 1, . . . , m}
+

+

−

−

dom(c [i]) = {0, 1, . . . , |D |}dom(c [i]) = {0, 1, . . . , |D |}dom(c[i]) = {0} ∪ {Nmin , Nmin + 1, . . . , |D|}+−dom(e[i]) = {0, 1, . . . , min{|D |, |D |}}∀i ∈ N D(6)∀i ∈ N(7)∀i ∈ N(8)∀i ∈ N L(9)∀i ∈ N(10)

Each decision node has a decision variable d (6) to model the decision feature.
Its value can be 0 (representing the dummy feature f0 ) or between 1 and m (representing one of the actual features f1 to fm ). Two counters, c+ (7) and c− (8),are defined for each node of the tree. They are used to keep track of how manytransactions respectively from D+ and D− match the decisions of the ancestorsof the node. A third counter c (9), defined at the leaves, tracks the total numberof transactions. The minimum number of transactions in each leaf is enforced by12Hélène Verhaeghe et al.

constraining the domain of c from Nmin to |D|. Value 0 also belongs to the domain
and is meant to be used only when the parent of the node is inactive (i.e. when its
decision is f0 ). An additional variable e (10), defined for each node, keeps track of
the error of the sub-tree rooted at that node. Our model does not have an explicit
variable for the class of the leaves. However, this can be easily deduced from thesolution by taking the class associated with the highest counter.

5.1.2 Constraints

On these variables, we define the following constraints:
c+ [i] + c− [i] = c[i]∀i ∈ N L(11)c [i] = c [left(i)] + c [right(i)]∀i ∈ ND(12)c− [i] = c− [left(i)] + c− [right(i)]∀i ∈ N D(13)e[i] = min{c [i], c [i]}∀i ∈ NL(14)

e[i] = e[left(i)] + e[right(i)]∀i ∈ N D(15)∀i ∈ NL(16)

CoverSizeSR(take(i), drop(i), c [i], D )∀i ∈ N

L(17)

AllDifferentExcept0({d[j] | j ∈ ancestors(i)} ∪ {d[i]})∀i ∈ N E

(18)

+

+

+

+

−

+

+

−

−

CoverSizeSR(take(i), drop(i), c [i], D )d[i] 6= 0 ⇒ min{c [i], c [i]} > e[i]∀i ∈ ND(19)d[i] = 0 ⇒ (d[left(i)] = 0 ∧ d[right(i)] = 0)∀i ∈ N N

(20)

+

−

First, constraint (11) links the counters at the leaves. Second, the counters at thedecision nodes are linked to the counters of their children (12, 13). Third, the valueof e[i] is assigned to be the minimum between the class counters (14) at the leaves
or to the sum of the errors from the children of i (15) for each of the decisionnodes. To compute the values of the counters c+ [i] and c− [i], we need to know
which transactions match the decisions of the ancestors of the leaf. To this end,
two CoverSizeSR global constraints (16, 17) are added at each leaf, one for eachclass. The decision variables of the ancestors (an ancestor is either the parent of
a node, either the parent of an ancestor) are divided into two distinct sets: The
take set take(i) = {d[j ] | j ∈ ancestors(i) ∧ left(j ) ∈ ancestors(i) ∪ {i}}, containing
the wanted features, and the drop set drop(i) = {d[j ] | j ∈ ancestors(i) ∧ right(j ) ∈ancestors(i) ∪ {i}}, containing the rejected features.
The next two constraints ensure the decision tree has no useless nodes. A
node is useless if the decision taken in it was already taken in one of the ancestor
nodes. An AllDifferentExcept0 (18) is used on the ancestors at each end-node
to avoid this. A node is also useless if all the leaves below have the same class. Thisis avoidable if we constrain the error at the node to be strictly higher than theerror of the subtree (19). Finally, when a decision node is inactive, all the decisionnodes below should be inactive as well (20).
These constraints are enough to guarantee an optimal, well-formed tree (withno dummy decision feature being a parent from a non-dummy decision and withno decision leading to only one classification).

Learning Optimal Decision Trees using Constraint Programming

13

5.1.3 Objective

The objective is to minimize the sum of the errors at the leaves, which is storedin e[root].
5.1.4 Redundant constraints

We add a number of redundant constraints to make the search more efficient:dom(c[i]) = {0} ∪ {Nmin , Nmin + 1, . . . , |D|}∀i ∈ N(21)

c+ [i] + c− [i] = c[i]∀i ∈ N(22)+

CoverSizeSR(take(i), drop(i), c [i], D )∀i ∈ N \areRight(N )(23)

CoverSizeSR(take(i), drop(i), c− [i], D− )∀i ∈ N \areRight(N )

(24)

+

+

c [i] < Nmin ⇒ d[i] = 0∀i ∈ ND(25)

c− [i] < Nmin ⇒ d[i] = 0∀i ∈ N D(26)c[i] < 2Nmin ⇒ d[i] = 0∀i ∈ ND(27)

d[i] 6= 0 ⇒ (c[left(i)] ≥ Nmin ∧ c[right(i)] ≥ Nmin )∀i ∈ N D(28)

Here, areRight(N ) = {i | i ∈ N ∧ i = right(parent(i))}; it represents the set ofnodes being the right child of another node.
Adding a constraint CoverSizeSR for all of the nodes in the tree allows thecomputation of the exact values of the counters earlier in the tree and therefore
helps prune earlier some candidate solutions. However adding them to all thedecision nodes is not necessary. Constraints (12) and (13) can be relied on tocompute the counters of one child based on the counters of the parent and thesibling. Constraints (23) and (24) are therefore used instead of (16) and (17).
This allows a better propagation while using the same number of CoverSizeSR
constraints. Constraints (25, 26) concern nodes with only transactions from oneclass left. When this arises, no decision should be taken in the node. As a minimum
number of transactions should be in each activated node, if a given decision node
does not have more than twice the threshold, no solution accepts a decision in thenode (27). The contrapositives of (25), (26), (27) are also logically true. Combined
together, they correspond to (28) which states that if the dummy decision is nolonger in the domain, there should be enough transactions in each of the children.
This constraint formulation requires to have the counter c (21) and the constraint
linking the counters at each node (22).

5.2 Search
The motivation behind the use of a specific search strategy is to exploit the treedecomposition into subproblems. During search each node of the search tree isassociated to a subtree of the decision tree being built. This subtree, identified by
the node id currProblem, is always rooted on a decision node. The assignment of
the decision variables occurs in top-down fashion. Therefore in a given node of thesearch tree, we can always assume every node in ancestors(currProblem) has been
assigned. Algorithm 3 details the pseudo-code of our algorithm.

14

Hélène Verhaeghe et al.
d[0] = fid[1] = fj1

d[0] = fid[2] = fk1

d[1] = fj2

d[0] = fid[1] = fj1

d[2] = fk2

d[0] = fid[2] = fk2

d[1] = fj2

d[2] = fk1(a) Independence of subtrees
d[0] = fj

d[0] = fid[1] = fj

d[2]

d[1]

d[0] = fj

d[2] = fid[1] = fid[2](b) Redundant subtrees; identically shaded subtrees are identicalFig. 4: Decompositions

OR nodeLeaf node
[0
]

d

le
ft

le
ft

[1
]=
0
d[1]
=1

1
[2
]=
0
d[2]
=

d

Part
SOL

i

Part
SOL

]=

H

Part

H
H

SOL

H

[2

...

d

i

]=
[1

d

1

d[2]?

d

i
]=

...

H

Part

H Part Part
H

SOL

H SOL SOL

t
gh

d[1]?

[2
d

]=
0
d[1]
=

1
ri

t
gh

i
]=

[1
d

d
[1

...

1

d[2]?

...

Part
SOL

1

ri

d[1]?

Part
SOL

2

1

]=

1

d[0]
=i

[0

1

d

=
2

d[0]?

=0 =1
d[0] d[0]

[2
]=
0
d[2]
=1

d[id]

0

d

AND noded[0]=3

depth

...

H

Part

H Part Part
H

SOL

H SOL SOL

H

Part

H
H

SOL

H

Fig. 5: AND/OR formulation of the search tree

5.2.1 Big picture.

Our search is the composition of three techniques: AND/OR search trees, branchand-bound optimization, and memorization. Each of them aims to answer one of
the specificities of the problem.
5.2.2 Subtree independence.

Given a subtree with its root decision and ancestors’ decisions assigned, its twochildren are totally independent from one another. Any solution from the left childcombined with any solution from the right child leads to a solution of the initial

Learning Optimal Decision Trees using Constraint Programming

15

Algorithm 3: AND/OR formulation with cache and minimum
pruning12Function search(currProblem: ∈ N D ):(Tree,Cost)
return ORnode(currProblem, ∞)Function ORnode(currProblem: ∈ N D ,costub ):(Tree,Cost)
prefix hash ← getPrefixHash(currProblem)
5if storage.contains(prefix hash) then// optimal already computed
6(solbest , costbest ) ← storage.get(prefix hash)7
return (solbest , costbest )8
else
9
costbest ← costub
10
solbest ← null
11
forall f ∈ dom(d[currProblem]) do// following value ordering
12
trail.pushState()
13
try
14
dom(d[currProblem]) ← {f }15dom(e[currProblem]) ← {v|v < costbest ∧ v ∈ dom(e[currProblem])}// pruning by minimisation
16
if currProblem ∈ N N then17(soltree , costtree ) ← ANDnode(currProblem, costbest , f )
18
else
19
soltree ← Tree(featureID : f left : null right : null)20
costtree ← e[currProblem].value
3
4

21
22
23

if costbest > costtree thencostbest ← costtree
solbest ← soltree

24

catch Inconsistency

25

trail.restoreState()// node have failed

26
27

storage.add(prefix hash, (solbest , costbest ))return (solbest , costbest )// new sol cached

Function ANDnode(currProblem: ∈ N D ,costub ,froot ):(Tree,Cost)(sollef t , costlef t ) ← ORnode(left(currProblem), costub )// 1st30
if costlef t > costub then31
return (null, ∞)// pruning based on cost
28
29

32
33
34

(solright , costright ) ← ORnode(right(currProblem), costub − costlef t )soltree ← Tree(featureID : froot left : sollef t right : solright )return (soltree , costlef t + costright )// 2ndsubtree. This is illustrated at Fig. 4a. However our goal is to find the best solution
and not one solution. Moreover our objective function is the sum of a cost computed in each of the leaves, independently. Therefore, the optimal solution, given aroot and ancestors’ decisions already assigned, can be computed independently bycomputing the optimal left child, then the optimal right child and finally combine
them. The AND/OR search tree [9, 14] framework is well suited for this kind of
decomposable problem. The search is composed of two types of search nodes: theOR nodes (line 3) and the AND nodes (line 28). An example of the search tree fora decision tree of depth 2 is shown at Fig. 5.
The AND node is responsible for computing the optimal value of the left child(line 29), then the right child (line 32), and finally returns the composed solution

16

Hélène Verhaeghe et al.

(line 33). The OR node tests all the possible values for the root decision variableof currProblem (line 11). The static ordering used to select the next value totest follows the principle of entropy [7]. The entropy of a set of transaction S is
computed using the number of transactions from each class, and is a well-known
heuristic in standard algorithms for learning decision trees:

Entropy (S ) = −|{t ∈ S : v [t] = 1}|
log2
|S|



|{t ∈ S : v [t] = 1}||S||{t ∈ S : v [t] = 0}|
log2
−
|S|





|{t ∈ S : v [t] = 0}|
|S|


(29)

The information gain of a feature f is the difference between the initial entropy
and the weighted entropy of a partition of the database into transactions with andwithout the feature:|{t ∈ D : Dt,f = 1}|
Entropy ({t ∈ D : Dt,f = 1})|D||{t ∈ D : Dt,f = 0}|−
Entropy ({t ∈ D : Dt,f = 0}).
|D|

Gain(f ) = Entropy (D) −(30)

The classification is expected to be better when the gain is higher. We sort thevalues by decreasing gain. This ordering is computed once at the beginning of thesearch and is reused at every search node. After assigning the selected value, if thesubtree still contains decision variables (i.e. if currProblem belongs to N N ), thenthe optimal subtrees are computed using an AND node (line 16). In the other case(i.e. if currProblem belongs to N E ), then we have already an optimal subtree (line18). From all the values tested, the best sub-tree is kept (line 21) and returned(line 27).

5.2.3 Subtree equality.

Two subproblems are equivalent whenever the set of decisions on the paths towards these nodes (the itemsets corresponding to the sets of decisions) are identical. Figure 4b shows how some subtrees can be the same in two different solutions due to paths that represent the same itemset. This is taken care of byusing a caching system similar to the one used in the DL8 dynamic programming approach [16]. Two subtrees are equivalent if they share the same assigned
prefix. The prefix of node i is composed of the values assigned to the decisionsof the ancestors. These values are separated in two distinct sets: The take set{d[j ] | j ∈ ancestors(i) ∧ left(j ) ∈ ancestors(i) ∪ {i}}, and the drop set {d[j ] | j ∈ancestors(i) ∧ right(j ) ∈ ancestors(i) ∪ {i}}. Two subtrees with the same take anddrop sets are thus equivalent. A hash is computed from these sets and serves as
key to store and retrieve the optimal subtree from storage (hashMap). In addition
to the decision in the root of the subtree, its cost is also stored, easing the computation. The search for an already computed solution happens at the beginningof an OR node (line 5). A new solution is stored when a new complete optimal
subtree is computed, i.e. at the end of the OR node (line 26).

Learning Optimal Decision Trees using Constraint Programming

17

5.2.4 Minimization.

In order to decrease the number of explored search nodes, a pruning by minimization is added to the search. At each of the search nodes, the upper bound of theallowed cost is propagated from node to node. During an OR node, this upperbound is decreased each time a better solution is found (line 21) and the best costfound so far is set as upper bound of the error of the subtree (line 15). During an
AND node, the propagated upper bound is first propagated to the computation of
the first child. If the result of this first child is above this propagated upper bound,then there is no need to compute the right child since any solution would be above
the propagated upper bound (line 30). This is triggered if the best solution was
already cached and has a higher cost than the bound or if there is no solution
with a cost smaller than the upper bound. An invalid subtree is then returned. If
the first child is lower than the upper bound, the second child can be computed
and the propagated upper bound for its computation is the difference between
the propagated upper bound of the tree and the cost of the already computed
tree (line 32). The search starts with an unbounded upper bound (∞). This is thedefault value if, prior to the search, no information is known about the optimalcost.
5.2.5 Implementation details

Oscar [18], the solver used in our experiment does not implement the AND/OR
search tree framework. A simple AND/OR search can be easily implemented using
a standard trail based solver [13]. The two main operations of a trailing system
are the saveState() and the restoreState() methods. The first one is responsible
for saving the current state of the solver and the second one to restore it. In atypical OR tree, a save is done before trying a new assignment and start a new
OR node. The state is restored when the node is fully explored. In an AND/OR
tree, the logic is the same. Algorithm 3 depicts, in the ORnode() method, where
the save and restore are being done. Just before trying a new assignment, atline 12, a save of the state is performed. Then the assignment is tested and thenode fully explored. The exploration of the node is embedded in an exception
catching mechanism. In case of inconsistencies (i.e. a proof of no solutions) during
the exploration of the node, an exception is thrown leading to the stop in the
exploration. After the exploration, a restoration of the state is required (line 25).
For further implementation details, the source code is available online2 .

6 Results

We compared our algorithm to two exact methods developed in earlier studies:
BinOCT [26] and DL8 [16], both of which solve exactly the same optimization
problem as our method. Notice that the optimal solution trees found by thesealgorithms are in most cases equal, therefore leading to the same model. Only inrare cases, two different trees are equally good. In any case, this can’t be used asa criterion to efficiently differentiate the prediction efficiently between the exact
2

https://bitbucket.org/helene_verhaeghe/classificationtree

18Hélène Verhaeghe et al.

methods since they are both able to output each an optimal tree. Both studies
have already evaluated the quality of the resulting trees experimentally. It was
shown in [3] that the more optimal is a tree on the training set, the more accurate
it is on a test set. These results were confirmed in [26, 16]. Therefore we decided
to focus our experiments on the run time performance of our algorithm, and noton the validation of the quality of the trees.

6.1 First benchmark

Datasetannealaudiology
australian-credit
breast-wisconsin
diabetes
german-credit
heart-cleveland
hepatitis
hypothyroid
ionospherekr-vs-kp
letterlymph
mushroom
pendigits
primary-tumor
segment
soybeansplice-1
tic-tac-toe
vehicle
vote
yeast
zoo-1

n

n+

n−

m

812
216
653
683
768
1000
296
137
3247
351
3196
20000
148
8124
7494
336
2310
630
3190
958
846
435
1484
101

625
57
357
444
500
700
160
111
2970
225
1669
813
81
4208
780
82
330
92
1655
626
218
267
463
41

187
159
296
239
268
300
136
26
277
126
1527
19187
67
3916
6714
254
1980
538
1535
332
628
168
1021
60

93
148
125
120
112
112
95
68
88
445
73
224
68
119
216
31
235
50
287
27
252
48
89
36

Table 1: Description of the instances

The benchmark3 is composed of instances from the CP4IM4 and UCI 5 websites. Their description is given at Table 1. BinOCT is a MIP-based approach running on CPLEX. It does not allow to give a specific value for Nmin . If a timeout isreached, the method outputs its best solution so far. We used the implementation
available online with as arguments the depth, the timeout (10 min) and a polishingtime (2.5 min). The polishing time is used to configure the CPLEX solver. At timeout minus the polishing time, CPLEX changes its search strategy. Polishing [22]is time consuming, but it allows improving a solution when the search stagnates.
DL8 is a dynamic programming approach. It computes a subset of the frequent
3

Available in the repository
https://dtai.cs.kuleuven.be/CP4IM/datasets/
5 https://archive.ics.uci.edu/ml/index.php
4Dataset

annealannealannealannealaudiology
audiology
audiology
audiology
australian-credit
australian-credit
australian-credit
breast-wisconsin
breast-wisconsin
breast-wisconsin
diabetes
diabetes
diabetes
german-credit
german-credit
german-credit
heart-clevelandheart-clevelandheart-clevelandheart-cleveland
hepatitis
hepatitis
hepatitis
hepatitis
hypothyroid
hypothyroid
hypothyroid
ionosphereionosphereionospherekr-vs-kp
kr-vs-kp
kr-vs-kp
kr-vs-kp
letterletterletterDepth

Learning Optimal Decision Trees using Constraint ProgrammingobjtNmin = 1
BinOCT
obj
t

2
3
4
5
2
3
4
5
2
3
4
2
3
4
2
3
4
2
3
4
2
3
4
5
2
3
4
5
2
3
4
2
3
4
2
3
4
5
2
3
4

137∗
112∗
∞
∞
10∗
5∗
∞
∞
87∗
73∗
∞
22∗
15∗
∞
177∗
162∗
∞
267∗
236∗
∞
60∗
41∗
25∗
∞
16∗
10∗
3∗
∞
70∗
61∗
∞
32∗
∞
∞
418∗
198∗
∞
∞
∞
∞
∞

1
37
TO
TO
<1
62
TO
TO
2
124
TO
2
103
TO
1
93
TO
2
129
TO
<1
17
515
TO
<1
4
54
TO
4
122
TO
50
TO
TO
2
74
TO
TO
TO
TO
TO

137∗
112
121
120
10∗
7
1
4
87∗
86
85
22∗
16
15
180
171
169
267
249
244
60∗
43
39
34
16∗
12
10
7
70∗
62
62
32
29
26
418
301
877
675
813
813
∞

DL8

206
TO
TO
TO
60
TO
TO
TO
206
TO
TO
44
TO
TO
TO
TO
TO
TO
TO
TO
312
TO
TO
TO
8
TO
TO
TO
178
TO
TO
TO
TO
TO
TO
TO
TO
TO
TO
TO
TO

19

CP
obj

t

137∗
112∗
91∗
84
10∗
5∗
1
0∗
87∗
73∗
57
22∗
15∗
7∗
177∗
162∗
137
267∗
236∗
204
60∗
41∗
25∗
9
16∗
10∗
3∗
0∗
70∗
61∗
53∗
32∗
22∗
13
418∗
198∗
144∗
81
599∗
369∗
294

<1
2
142
TO
<1
5
TO
3
<1
9
TO
<1
6
493
<1
8
TO
<1
8
TO
<1
4
265
TO
<1
1
49
8
<1
4
183
1
328
TO
<1
2
107
TO
1
108
TO

Table 2: Results (part 1) Time out (TO) = 10 min, best value (objective (obj,
in number of wrongly classified transactions) or time (t, in seconds)) for a given
Nmin = 1 in bold, optimal obj proven indicated with ∗itemsets and then builds the optimal tree from it. This approach does not output
any intermediate non-optimal tree. We used the implementation provided by theauthors with as arguments the depth and the minimum support (value of Nmin ).
The Table 2 and Table 3 shows the results for the three methods (DL8, BinOCT
and ours) with Nmin = 1 using a timeout of 10 mins. The second part of Table 4 andTable 5 shows the results for two methods (DL8 and ours) and some variationsof our approach (without the caching, labelled CP-c, and without the pruning

Hélène Verhaeghe et al.
Dataset

lymph
lymph
lymph
lymph
mushroommushroommushroom
pendigits
pendigits
pendigits
primary-tumor
primary-tumor
primary-tumor
primary-tumor
segment
segment
segment
soybeansoybeansoybeansoybeansplice-1
splice-1
splice-1
tic-tac-toe
tic-tac-toe
tic-tac-toe
tic-tac-toe
vehiclevehiclevehicle
vote
vote
vote
vote
yeast
yeast
yeast
zoo-1

Depth

20

obj

t

2
3
4
5
2
3
4
2
3
4
2
3
4
5
2
3
4
2
3
4
5
2
3
4
2
3
4
5
2
3
4
2
3
4
5
2
3
4
2

22∗
12∗
3∗
∞
252∗
∞
∞
∞
∞
∞
58∗
46∗
34∗
26∗
9∗
∞
∞
55∗
29∗
14∗
8∗
508∗
∞
∞
282∗
216∗
137∗
63∗
75∗
∞
∞
17∗
12∗
5∗
1∗
437∗
403∗
∞
0∗

<1
2
43
TO
27
TO
TO
TO
TO
TO
<1
<1
2
14
49
TO
TO
<1
2
33
315
143
TO
TO
<1
<1
3
16
23
TO
TO
<1
2
23
248
2
74
TO
<1

DL8

Nmin = 1
BinOCT
obj
t

obj

t

22∗
13
8
8
520
396
160
153
496
780
58∗
49
39
37
9
6
21
55∗
42
16
24
522
574
1087
282∗
231
169
128
75
60
84
17∗
13
11
5
437
430
412
0∗

22∗
12∗
3∗
0∗
252∗
8∗
0∗
153∗
47∗
14
58∗
46∗
34∗
26∗
9∗
0∗
0∗
55∗
29∗
14∗
8∗
508∗
224∗
141
282∗
216∗
137∗
63∗
75∗
26∗
13
17∗
12∗
5∗
1∗
437∗
403∗
366∗
0∗

<1
1
42
1
<1
4
<1
1
50
TO
<1
<1
4
71
<1
2
1
<1
1
14
497
<1
125
TO
<1
<1
3
64
<1
45
TO
<1
1
16
394
<1
6
287
<1

17
TO
TO
TO
TO
TO
TO
TO
TO
TO
5
TO
TO
TO
TO
TO
TO
19
TO
TO
TO
TO
TO
TO
10
TO
TO
TO
TO
TO
TO
8
TO
TO
TO
TO
TO
TO
<1

CP

Table 3: Results (part 2) Time out = 10 min, best value (objective (obj, in numberof wrongly classified transactions) or time (t, in seconds)) for a given Nmin = 1 inbold, optimal obj proven indicated with ∗using bounds, labelled CP-m) with Nmin = 5 using a timeout of 10 mins. This
comparison does not include BinOCT since its implementation cannot take into
account Nmin . A value of 5 is chosen, as this yields results that are more statisticallysignificant. Table 6 summarizes our results. For each of the algorithms, the numberof instances where the optimality is proven, the solution found is the best among
the tested algorithms, the algorithm was the fastest and timeout is reached aregathered.

Learning Optimal Decision Trees using Constraint Programmingannealannealannealannealaudiology
audiology
audiology
audiology
australian-credit
australian-credit
australian-credit
breast-wisconsin
breast-wisconsin
breast-wisconsin
diabetes
diabetes
diabetes
german-credit
german-credit
german-credit
heart-clevelandheart-clevelandheart-clevelandheart-cleveland
hepatitis
hepatitis
hepatitis
hepatitis
hypothyroid
hypothyroid
hypothyroid
ionosphereionosphereionospherekr-vs-kp
kr-vs-kp
kr-vs-kp
kr-vs-kp
letterletterletterNmin = 5

Depth

Dataset

21

obj

t

obj

t

obj

t

2
3
4
5
2
3
4
5
2
3
4
2
3
4
2
3
4
2
3
4
2
3
4
5
2
3
4
5
2
3
4
2
3
4
2
3
4
5
2
3
4

137∗
112∗
94∗
∞
11∗
7∗
4∗
1∗
87∗
74∗
∞
22∗
15∗
∞
177∗
162∗
∞
267∗
236∗
∞
60∗
41∗
27∗
∞
16∗
11∗
8∗
5∗
70∗
62∗
∞
32∗
∞
∞
418∗
198∗
∞
∞
∞
∞
∞

<1
31
591
TO
<1
2
43
512
2
90
TO
3
80
TO
1
90
TO
2
122
TO
<1
15
404
TO
<1
2
36
299
3
95
TO
48
TO
TO
2
63
TO
TO
TO
TO
TO

137∗
112∗
94∗
92
11∗
7∗
4∗
1∗
87∗
74∗
60
22∗
15∗
9
177∗
162∗
138
267∗
236∗
205
60∗
41∗
27∗
17
16∗
11∗
8∗
6
70∗
62∗
54∗
32∗
22∗
16
418∗
198∗
144∗
98
599∗
369
296

<1
3
172
TO
<1
1
56
534
<1
11
TO
<1
8
TO
<1
10
TO
<1
11
TO
<1
5
333
TO
<1
1
62
TO
<1
4
236
1
389
TO
<1
4
214
TO
5
TO
TO

137∗
112∗
94∗
92
11∗
7∗
4∗
1∗
87∗
74∗
66
22∗
15∗
9
177∗
162∗
138
267∗
236∗
205
60∗
41∗
27∗
17
16∗
11∗
8∗
6
70∗
62∗
54∗
32∗
22∗
16
418∗
198∗
144∗
98
599∗
369
296

<1
3
257
TO
<1
1
55
475
<1
12
TO
<1
8
TO
<1
11
TO
<1
13
TO
<1
8
528
TO
<1
2
86
TO
<1
4
323
1
443
TO
<1
4
256
TO
5
TO
TO

DL8

CP

CP-c

CP-m
obj
t
137∗
112∗
94∗
92
11∗
7∗
4∗
1
87∗
74∗
66
22∗
15∗
9
177∗
162∗
138
267∗
236∗
205
60∗
41∗
27∗
18
16∗
11∗
8∗
8
70∗
62∗
54∗
32∗
22
16
418∗
198∗
144∗
132
599∗
531
301

<1
4
296
TO
<1
2
74
TO
<1
14
TO
<1
12
TO
<1
13
TO
<1
14
TO
<1
7
595
TO
<1
2
99
TO
<1
8
570
1
TO
TO
<1
7
483
TO
5
TO
TO

Table 4: Results (part 1) Time out (TO) = 10 min, best value (objective (obj,
in number of wrongly classified transactions) or time (t, in seconds)) for a given
Nmin = 5 in bold, optimal obj proven indicated with ∗Our method outperforms the two others on most of the instances. It could findand prove optimality on roughly 83% of the instances within the time limit. The
best solution found was reached by our method in almost every cases. However,DL8 performs better on small instances such as hepatitis, lymph or primary-tumor.
The large difference between BinOCT and our method can be explained by thebenefits of the AND/OR search that is not used by BinOCT. The gap with DL8
can be partially explained by the cost pruning. It can possibly also be explainedby the itemset mining algorithms used: DL8 lacks the optimizations found in the
CoverSize constraint [23].

22

lymph
lymph
lymph
lymph
mushroommushroommushroom
pendigits
pendigits
pendigits
primary-tumor
primary-tumor
primary-tumor
primary-tumor
segment
segment
segment
soybeansoybeansoybeansoybeansplice-1
splice-1
splice-1
tic-tac-toe
tic-tac-toe
tic-tac-toe
tic-tac-toe
vehiclevehiclevehicle
vote
vote
vote
vote
yeast
yeast
yeast
zoo-1

Nmin = 5

Depth

DatasetHélène Verhaeghe et al.

obj

t

obj

t

obj

t

2
3
4
5
2
3
4
2
3
4
2
3
4
5
2
3
4
2
3
4
5
2
3
4
2
3
4
5
2
3
4
2
3
4
5
2
3
4
2

22∗
13∗
7∗
4∗
252∗
∞
∞
∞
∞
∞
58∗
46∗
40∗
34∗
9∗
∞
∞
55∗
29∗
15∗
13∗
508∗
∞
∞
282∗
216∗
137∗
63∗
75∗
∞
∞
18∗
13∗
6∗
3∗
437∗
403∗
∞
0∗

<1
1
15
166
24
TO
TO
TO
TO
TO
<1
<1
1
8
41
TO
TO
<1
2
27
239
89
TO
TO
<1
<1
3
16
20
TO
TO
<1
1
13
118
2
70
TO
<1

22∗
13∗
7∗
4∗
252∗
8∗
0∗
153∗
47∗
15
58∗
46∗
40∗
34∗
9∗
2∗
0∗
55∗
29∗
15∗
13
508∗
225∗
142
282∗
216∗
137∗
63∗
75∗
28∗
17
18∗
13∗
6∗
3∗
437∗
403∗
367∗
0∗

<1
1
34
595
<1
15
<1
2
256
TO
<1
<1
4
65
1
69
186
<1
1
21
TO
1
156
TO
<1
<1
7
83
<1
83
TO
<1
1
17
234
<1
7
421
<1

22∗
13∗
7∗
4
252∗
8∗
0∗
153∗
47∗
19
58∗
46∗
40∗
34∗
9∗
2∗
0∗
55∗
29∗
15∗
13
508∗
225∗
142
282∗
216∗
137∗
63∗
75∗
28∗
17
18∗
13∗
6∗
3∗
437∗
403∗
367
0∗

<1
2
40
TO
<1
15
<1
2
268
TO
<1
<1
6
162
<1
71
181
<1
1
26
TO
1
188
TO
<1
<1
9
282
<1
85
TO
<1
1
20
300
<1
9
TO
<1

DL8

CP

CP-c

CP-m
obj
t
22∗
13∗
7∗
4
252∗
8∗
0
153∗
47∗
19
58∗
46∗
40∗
34∗
9∗
2∗
0
55∗
29∗
15∗
13
508∗
225∗
142
282∗
216∗
137∗
63∗
75∗
28∗
17
18∗
13∗
6∗
4
437∗
403∗
367∗
0∗

<1
2
59
TO
<1
44
TO
2
415
TO
<1
<1
5
104
1
136
TO
<1
1
35
TO
1
249
TO
<1
<1
5
167
1
143
TO
<1
1
41
TO
<1
7
541
<1

Table 5: Results (part 2) Time out = 10 min, best value (objective (obj, in numberof wrongly classified transactions) or time (t, in seconds)) for a given Nmin = 5 inbold, optimal obj proven indicated with ∗Proven optimality
Best solution foundFastestTime out

DL8

Nmin = 1
BinOCTCP

DL849(61%)
49(61%)
17(21%)
31(39%)

13(16%)
21(26%)1(1%)
67(84%)

68(85%)
80(100%)63(79%)
12(15%)

54(67%)
54(67%)
26(32%)
25(31%)

Nmin = 5CPCP-c65(81%)
79(99%)
52(65%)
15(19%)

Table 6: Summary of the results

63(79%)
77(96%)
36(45%)
17(21%)

CP-m
59(74%)
72(90%)
27(34%)
21(26%)

Learning Optimal Decision Trees using Constraint Programming

23

Finally, the effects of the cache and the pruning using the best known partial
solutions can be observed. CP-c gives the results of our method when the cachesystem is not used and CP-m gives the results when the pruning using the best
partial solution is not used. The cache becomes really useful at depth 4 (or more)
and some instances greatly benefit from it (e.g. the tic-tac-toe benchmark witha depth of 5 improves its timing by 70% when adding the cache). The effect ofthe pruning is significant in some cases. On some benchmarks such as mushroom,
hypothyroid, ionosphere or vehicle, the pruning improves greatly the solution (ex.
on hypothyroid depth 4, the time is divided by 2.4). This improvement indicatesthat when searching for the best subtree, the best one is found early, prunning afair amount of the search space concerning the subtree.

6.2 Second benchmark

Dataset

n

n+

n−

m

dexterdorothea
dota2

300
800
92650

150
78
48782

150
722
43868

25736
100000226

Table 7: Description of the instances (after binarization)

dexterdexterdexterdexterdorothea
dorothea
dota2
dota2

Nmin = 1

Depth

Dataset

obj

t

obj

t

2
3
4
5
2
3
2
3

∞
∞
∞
∞
∞
∞
∞
∞

TO
TO
TO
TO
TO
TO
TO
TO

135
129
124
120
39
78
42610∗
42107

TO
TO
TO
TO
TO
TO
33
TO

DL8

CP

Table 8: Results (part 3) Time out = 20 min, best value (objective (obj, in numberof wrongly classified transactions) or time (t, in seconds)) for a given Nmin = 1 inbold, optimal obj proven indicated with ∗To evaluate the scaling of our method, we tested it on some bigger instancesfrom the UCI website. The description of these instances is available in Tab. 7.
The results with Nmin = 1 are available in Tab. 8 and with Nmin = 5 Tab. 8.
A timeout of 20 minutes was used for these instances. These datasets required
binarization first6 .
6Binarized versions available in the repository

24

dexterdexterdexterdexterdorothea
dorothea
dota2
dota2

Nmin = 5

Depth

DatasetHélène Verhaeghe et al.

obj

t

obj

t

obj

t

obj

t

2
3
4
5
2
3
2
3

136∗
130∗
125∗
120∗
∞
∞
∞
∞

13
99
100
1066
TO
TO
TO
TO

136∗
130∗
125∗
120
39
78
42610∗
42107

12
264
849
TO
TO
TO
97
TO

136∗
130∗
125∗
120
39
78
42610∗
42107

12
260
829
TO
TO
TO
100
TO

136∗
130∗
125∗
120
39
78
42610∗
42107

15
198
602
TO
TO
TO
124
TO

DL8

CP

CP-c

CP-m

Table 9: Results (part 3) Time out = 20 min, best value (objective (obj, in numberof wrongly classified transactions) or time (t, in seconds)) for a given Nmin = 5 inbold, optimal obj proven indicated with ∗As shown by the dota2 instance, in the line of the letter instance of the firstbenchmark, increasing the number of transactions affects less our algorithm thanDL8. This is due to the use of the bitsets inside the CoverSize constraint. The
dexter instance allows us to see that good performance can be achieved with a
big number of features. Unfortunately, with too many features, as shown on the
dorothea instance, even a depth-2 tree is not obtainaible within time out.

7 Conclusion

We presented a new approach for efficiently creating an optimal decision tree oflimited depth. On most of the benchmarks, it gives the best solution within the
allocated time and is the fastest to prove optimality.
We believe our approach can be extended in a number of different ways. It
is straightforward to extend it to the multiclass setting, by adding counters andCoverSizeSR constraints for each of the additional classes. We assumed the input
data was binary; if the data is not binary, it can be binarized beforehand [6]. Of
particular interest can also be addition of further constraints and the use of othercost functions that can be expressed as a sum of costs at the leaves.

RemarkThis paper is an extended and improved version of the paper initially accepted
to CP2019 in the journal fast track. The initial work was also presented in a 2page summary abstract [24] at BNAIC2019, a national conference, and as a 4-page
summary abstract [25], in the sister conference track at IJCAI20.

References
1. Aghaei, S., Azizi, M.J., Vayanos, P.: Learning optimal and fair decision trees for nondiscriminative decision-making (2019)

Learning Optimal Decision Trees using Constraint Programming25

2. Babaki, B., Guns, T., De Raedt, L.: Stochastic constraint programming with and-or
branch-and-bound. In: Proceedings of the Twenty-Sixth International Joint Conference on
Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, pp. 539–545(2017)
3. Bertsimas, D., Dunn, J.: Optimal classification trees. Machine Learning 106(7), 1039–1082(2017)
4. Bessiere, C., Hebrard, E., O’Sullivan, B.: Minimising decision tree size as combinatorial optimisation. In: I.P. Gent (ed.) Principles and Practice of Constraint Programming - CP 2009, 15th International Conference, CP 2009, Lisbon, Portugal, September
20-24, 2009, Proceedings, Lecture Notes in Computer Science, vol. 5732, pp. 173–187.
Springer (2009). DOI 10.1007/978-3-642-04244-7\ 16. URL https://doi.org/10.1007/
978-3-642-04244-7\_16
5. Bonfietti, A., Lombardi, M., Milano, M.: Embedding decision trees and random forests
in constraint programming. In: L. Michel (ed.) Integration of AI and OR Techniquesin Constraint Programming - 12th International Conference, CPAIOR 2015, Barcelona,
Spain, May 18-22, 2015, Proceedings, Lecture Notes in Computer Science, vol. 9075, pp.
74–90. Springer (2015). DOI 10.1007/978-3-319-18008-3\ 6. URL https://doi.org/10.
1007/978-3-319-18008-3\_6
6. Breiman, L.: Classification and regression trees. Routledge (1984)
7. Cover, T.M., Thomas, J.A.: Elements of information theory. John Wiley & Sons (2012)
8. Dechter, R., Mateescu, R.: The impact of AND/OR search spaces on constraint satisfaction
and counting. In: Principles and Practice of Constraint Programming - CP 2004, 10th
International Conference, CP 2004, Toronto, Canada, September 27 - October 1, 2004,
Proceedings, pp. 731–736 (2004)
9. Dechter, R., Mateescu, R.: And/or search spaces for graphical models. Artificial intelligence 171(2-3), 73–106 (2007)
10. Demeulenaere, J., Hartert, R., Lecoutre, C., Perez, G., Perron, L., Régin, J.C., Schaus,P.: Compact-table: efficiently filtering table constraints with reversible sparse bit-sets. In:
International Conference on Principles and Practice of Constraint Programming, pp. 207–223. Springer (2016)
11. Hancock, T., Jiang, T., Li, M., Tromp, J.: Lower bounds on learning decision lists andtrees. Information and Computation 126(2), 114–122 (1996)
12. Hyafil, L., Rivest, R.L.: Constructing optimal binary decision trees is np-complete. Inf.
Process. Lett. 5(1), 15–17 (1976). DOI 10.1016/0020-0190(76)90095-8. URL https://doi.org/10.1016/0020-0190(76)90095-8
13. Laurent Michel, Pierre Schaus, Pascal Van Hentenryck: MiniCP: A lightweight solver forconstraint programming (2018). Available from https://minicp.bitbucket.io
14. Marinescu, R., Dechter, R.: And/or tree search for constraint optimization. In: Proc. of
the 6th International Workshop on Preferences and Soft Constraints. Citeseer (2004)
15. Narodytska, N., Ignatiev, A., Pereira, F., Marques-Silva, J.: Learning optimal decision
trees with SAT. In: J. Lang (ed.) Proceedings of the Twenty-Seventh International Joint
Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden,
pp. 1362–1368. ijcai.org (2018). DOI 10.24963/ijcai.2018/189. URL https://doi.org/10.
24963/ijcai.2018/189
16. Nijssen, S., Fromont, E.: Mining optimal decision trees from itemset lattices. In: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data
mining, pp. 530–539. ACM (2007)
17. Nijssen, S., Fromont, É.: Optimal constraint-based decision tree induction from itemset
lattices. Data Min. Knowl. Discov. 21(1), 9–51 (2010)
18. OscaR
Team:
OscaR:
ScalainOR(2012).
Availablefromhttps://bitbucket.org/oscarlib/oscar
19. Quinlan, J.R.: Induction of decision trees. Mach. Learn. 1(1), 81–106 (1986). DOI
10.1023/A:1022643204877. URL https://doi.org/10.1023/A:1022643204877
20. Quinlan, J.R.: C4.5: Programs for Machine Learning. Morgan Kaufmann (1993)
21. Rossi, F., Van Beek, P., Walsh, T.: Handbook of constraint programming. Elsevier (2006)
22. Rothberg, E.: An evolutionary algorithm for polishing mixed integer programming solutions. INFORMS Journal on Computing 19(4), 534–541 (2007)
23. Schaus, P., Aoga, J.O., Guns, T.: Coversize: a global constraint for frequency-based itemset
mining. In: International Conference on Principles and Practice of Constraint Programming, pp. 529–546. Springer (2017)26

Hélène Verhaeghe et al.

24. Verhaeghe, H., Nijssen, S., Pesant, G., Quimper, C., Schaus, P.: Learning optimal decision
trees using constraint programming. In: K. Beuls, B. Bogaerts, G. Bontempi, P. Geurts,
N. Harley, B. Lebichot, T. Lenaerts, G. Louppe, P.V. Eecke (eds.) Proceedings of the
31st Benelux Conference on Artificial Intelligence (BNAIC 2019) and the 28th Belgian
Dutch Conference on Machine Learning (Benelearn 2019), Brussels, Belgium, November
6-8, 2019, CEUR Workshop Proceedings, vol. 2491. CEUR-WS.org (2019). URL http://ceur-ws.org/Vol-2491/abstract109.pdf
25. Verhaeghe, H., Nijssen, S., Pesant, G., Quimper, C., Schaus, P.: Learning optimal decision
trees using constraint programming (extended abstract). In: Proceedings of the TwentyNinth International Joint Conference on Artificial Intelligence, IJCAI 2020, Tokyo, Japan,
2020 (2020)
26. Verwer, S., Zhang, Y.: Learning optimal classification trees using a binary linear program
formulation. In: The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI
2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI
2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence,
EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019, pp. 1625–1632. AAAI
Press (2019). DOI 10.1609/aaai.v33i01.33011624. URL https://doi.org/10.1609/aaai.
v33i01.33011624