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

원문 초록

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.