math.OCNov 8, 2026

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

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.

Figures & tables

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. An Exact Junction-Tree Extended Formulation for Optimal Classification Trees

    Sep 21, 2026Jiancheng TU, WenqiFanDecision Tree LearningClassification

  2. Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction

    Sep 5, 2026Jiancheng Tu, Wenqi FanDecision Tree LearningDynamic Programming

  3. Search Strategies for Optimal Classification and Regression Trees

    Jul 30, 2026Jacobus G. M. van der Linden, Mim van den Bos, Emir DemirovićDecision Tree LearningClassification