Recursive Pricing and Incumbent Subtree Column Generation for Solving Optimal Classification Trees
Authors: Tengmu Hu, Chen Chen, Theodore T. Allen
Organizations: Supply Chain, Operations, and Technology, Olin Business School, Washington University in St. Louis · Integrated Systems Engineering, The Ohio State University · Industrial and Systems Engineering, University of Massachusetts Amherst
Solving optimal classification tree (OCT) problems is computationally challenging because branching, routing, and leaf-assignment decisions must be optimized jointly. We develop an incumbent subtree column generation algorithm (ISCG-OCT) that exploits the recursive structure of classification trees. We first introduce a mixed set-packing and set-partitioning formulation (MSSF). We then construct a restricted master problem whose columns represent feasible subtree patterns. Unlike conventional dual-based column generation, our incumbent-centered pricing evaluates objective improvements relative to the current solution. We establish a recursive decomposition in which fixing a branching decision separates the remaining pricing problem into independent subtree subproblems, enabling exact dynamic programming. We also develop threshold-based variants that trade optimality guarantees for computational efficiency. Computational experiments on 27 benchmark datasets demonstrate competitive training and testing accuracy and substantial reductions in solution time on many instances. When initialized with a CART solution, ISCG-OCT can certify global optimality faster than warm-started mixed-integer programming solvers on selected instances. These results demonstrate how recursive pricing and structured subtree optimization can improve the computational efficiency of exact classification tree methods.
Figures & tables
Figure 1: Example of the structure of a classification tree. Node v2 is the parent of leaf nodes t3 and t4 , where t3 is the left child of v2 and t4 is the right child of v2 .
Figure 2: Training Accuracy Performance Profiles for Tree Depths D=2,3,4,5 (Time Limit of 3,600 Seconds)
Figure 3: Testing Accuracy Performance Profiles for Tree Depths D=2,3,4,5 (Time Limit of 3,600 Seconds)
Figure 4: computational times Performance Profiles for Tree Depths D=2,3,4,5 (Time Limit of 3,600 Seconds)
Figure 5: Optimality Gap Profiles for Tree Depths D=2,3,4,5 (Gaps Relative to Each Method’s Formulation)
Appendix figures & tables10 assets
Supplementary material from the paper’s appendix.
Appendix
Figure A.1: Recursive Class-Boundary Candidate Split Construction with Three Features (Both Values Adjacent to Each Class Transition Are Retained When They Induce Nontrivial Splits, with the Artificial Lower and Upper Boundary Values)
Observation
1
2
3
4
5
6
7
8
x1
1
1
2
2
4
4
5
5
x2
1
4
2
5
1
4
2
5
Class
A
B
A
B
B
A
B
A
Appendix
Table A.1: Toy Binary-Classification Dataset
MIP-based
ISCG-OCT
Dataset
BNP- OCT
Benders OCT
OCT
STreeD
U=0%
U=5%
(a) Depth D=2
Seismic-bumps
0.94
0.94
0.93
0.94
0.94
0.94
Thoracic Surgery
0.88
0.88
0.87
0.88
0.88
0.87
House-vote
0.97
0.97
0.96
0.97
0.97
0.97
Mushroom
0.98
0.98
0.97
0.96
0.98
0.94
Appendix
Table A.2: Training Accuracy for D=2 and D=3
MIP-based
ISCG-OCT
Dataset
BNP- OCT
Benders OCT
OCT
STreeD
U=0%
U=5%
(a) Depth D=4
Seismic-bumps
0.94
0.94
0.94
0.94
0.94
0.94
Thoracic Surgery
0.89
0.88
0.89
0.93
0.89
0.88
House-vote
0.99
1.00
0.99
1.00
1.00
0.98
Mushroom
0.81
0.93
0.85
1.00
0.98
0.98
Appendix
Table A.3: Training Accuracy for D=4 and D=5
MIP-based
ISCG-OCT
Dataset
BNP- OCT
Benders OCT
OCT
STreeD
U=0%
U=5%
(a) Depth D=2
Seismic-bumps
0.93
0.93
0.93
0.93
0.92
0.93
Thoracic Surgery
0.82
0.84
0.84
0.79
0.82
0.82
House-vote
0.97
0.97
0.99
0.97
0.97
0.97
Mushroom
0.98
0.89
0.97
0.96
0.87
0.94
Appendix
Table A.4: Testing Accuracy for D=2 and D=3
MIP-based
ISCG-OCT
Dataset
BNP- OCT
Benders OCT
OCT
STreeD
U=0%
U=5%
(a) Depth D=4
Seismic-bumps
0.93
0.93
0.93
0.93
0.92
0.93
Thoracic Surgery
0.83
0.84
0.80
0.79
0.81
0.81
House-vote
0.96
0.96
0.99
0.96
0.96
0.91
Mushroom
0.80
0.93
0.86
1.00
0.89
0.97
Appendix
Table A.5: Testing Accuracy for D=4 and D=5
MIP-based
ISCG-OCT
Dataset
BNP- OCT
Benders OCT
OCT
STreeD
U=0%
U=5%
(a) Depth D=2
Seismic-bumps
3600.00
1592.23
3600.00
10.00
1631.12
4.12
Thoracic Surgery
328.28
72.32
3600.00
0.03
0.82
0.42
House-vote
1.43
3.24
6.71
0.00
0.11
0.01
Mushroom
3600.00
7.23
3600.00
0.05
0.05
0.05
Appendix
Table A.6: Running Times (Seconds) for D=2 and D=3
MIP-based
ISCG-OCT
Dataset
BNP- OCT
Benders OCT
OCT
STreeD
U=0%
U=5%
(a) Depth D=4
Seismic-bumps
3600.00
3600.00
3600.00
3600.00
3600.00
8.52
Thoracic Surgery
3600.00
3231.56
3600.00
33.30
0.81
0.34
House-vote
802.57
37.85
3600.00
0.02
0.03
0.03
Mushroom
3600.00
3600.00
3600.00
1.35
14.52
0.03
Appendix
Table A.7: Running Times (Seconds) for D=4 and D=5
MIP-based
ISCG-OCT
Dataset
BNP- OCT
Benders OCT
OCT
STreeD
U=0%
U=5%
(a) Depth D=2
Seismic-bumps
99%
0%
97%
0%
0%
0%
Thoracic Surgery
0%
0%
0%
0%
0%
100%
House-vote
0%
0%
0%
0%
0%
0%
Mushroom
67%
0%
67%
0%
0%
99%
Appendix
Table A.8: Reported Optimality Gaps for D=2 and D=3
MIP-based
ISCG-OCT
Dataset
BNP- OCT
Benders OCT
OCT
STreeD
U=0%
U=5%
(a) Depth D=4
Seismic-bumps
99%
100%
98%
100%
98%
98%
Thoracic Surgery
99%
0%
99%
0%
0%
100%
House-vote
0%
0%
0%
0%
0%
100%
Mushroom
98%
95%
100%
0%
0%
0%
Appendix
Table A.9: Reported Optimality Gaps for D=4 and D=5
We develop an exact linear programming (LP) formulation for bounded-depth classification trees with binary features, using a junction-tree representation. The formulation is integral and supports recursive subtree optimization. Exact reductions make the model smaller while preserving the optimal value and recovery of an optimal tree. The reduced model supports two solution methods: column generation and message passing. Column generation solves integral restricted LPs and uses bounds over the full feasible domain to certify optimality. Message passing recursively combines optimal subtree costs. Both methods solve common subtree problems that, once the preceding tree decisions are fixed, can be evaluated independently and in parallel. Computational experiments show that the exact reductions substantially reduce the size of the junction-tree formulation. The resulting linear programming formulation certifies instances for which the tested mixed-integer formulation does not establish optimality within the same computational budget, while the column-generation and message-passing methods certify more instances and achieve an order-of-magnitude reduction in geometric-mean runtime relative to an existing state-of-the-art exact method for optimal classification trees.
Jiancheng TU, WenqiFan
Department of Computing, The Hong Kong Polytechnic University · Department of Management and Marketing, The Hong Kong Polytechnic University
Dynamic programming for optimal classification trees becomes computationally expensive as the numbers of features and training samples increase. We develop a joint feature- and sample-space reduction framework based on STreeD. Weighted STreeD merges duplicate records created after projection onto a fixed candidate set into weighted representatives. This reduces sample-dependent computation without changing the fixed-candidate optimization problem. Adaptive STreeD repeatedly refines a bounded candidate set, retains features used by the incumbent tree, rebuilds the weighted representation, and solves the resulting reduced problems. Each certified Weighted STreeD solution is optimal for its current candidate set, while the outer feature search remains heuristic over the full feature space. Experiments on five data sets show that Weighted STreeD achieves speedups of up to 121.41 times over standard STreeD. Adaptive STreeD reduces runtime in matched comparisons at depths 2 to 4 and continues to return feasible trees at greater depths where full-feature methods are limited by time or memory. Under the same computational budget, its predictive performance remains comparable to the evaluated optimal classification tree baselines and is higher in some comparisons. These results show how joint feature- and sample-space reduction can scale dynamic-programming-based optimal-tree learning to more demanding instances.
Jiancheng Tu, Wenqi Fan
Department of Computing, The Hong Kong Polytechnic University · Department of Management and Marketing, The Hong Kong Polytechnic University
Optimal decision trees (ODTs) are compact, interpretable machine learning models that globally optimize a given objective, but their scalability remains challenging. While recent work has proposed a variety of search strategies to improve scalability, the precise contribution of each strategy remains unclear. To address this gap, we introduce a general algorithmic framework for ODTs that instantiates previously used search strategies and enables the definition of new ones. This provides a common lens through which to understand and compare different strategies, which we use to empirically investigate the effect of 18 search strategies. Compared to the state of the art, the best strategy in our evaluation achieves significantly better anytime performance for classification, and improves runtime by more than an order of magnitude for regression.
Jacobus G. M. van der Linden, Mim van den Bos, Emir Demirović