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