# Recursive Pricing and Incumbent Subtree Column Generation for Solving Optimal Classification Trees

DevFeed: [Recursive Pricing and Incumbent Subtree Column Generation for Solving Optimal Classification Trees](<https://devfeed.tech/articles/recursive-pricing-and-incumbent-subtree-column-generation-for-solving-optimal-classification-trees-125415.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.11578>)

Author: Tengmu Hu, Chen Chen, Theodore T. Allen

Published: 2026-11-10T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [Operations research and optimization](<https://devfeed.tech/topics/operations-research-and-optimization.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [classification](<https://devfeed.tech/tags/classification.md>), [column](<https://devfeed.tech/tags/column.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [dynamic-programming](<https://devfeed.tech/tags/dynamic-programming.md>), [efficiency](<https://devfeed.tech/tags/efficiency.md>), [experiments](<https://devfeed.tech/tags/experiments.md>), [exploits](<https://devfeed.tech/tags/exploits.md>), [generation](<https://devfeed.tech/tags/generation.md>), [guarantees](<https://devfeed.tech/tags/guarantees.md>), [math-oc](<https://devfeed.tech/tags/math-oc.md>), [pricing](<https://devfeed.tech/tags/pricing.md>), [trees](<https://devfeed.tech/tags/trees.md>)

## AI overview

ISCG-OCT uses incumbent-centered subtree column generation to improve exact optimal classification tree solving. Its mixed set-packing and set-partitioning formulation represents feasible subtree patterns as master-problem columns; pricing measures objective improvement against the current solution. Fixing a branching decision splits pricing into independent subtree problems, solved by exact dynamic programming. Threshold-based variants improve computational efficiency while trading away optimality guarantees. Experiments on 27 benchmark datasets report competitive training and testing accuracy and substantial solution-time reductions on many instances. Initialized with CART, the method certifies global optimality faster than warm-started mixed-integer programming solvers on selected instances.

## Source excerpt

arXiv:2611.11578v1 Announce Type: cross Abstract: 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.