SOURCE-LINKED INTELLIGENCE

An Exact Junction-Tree Extended Formulation for Optimal Classification Trees

arXiv · AI, language, vision and robotics · article · Sep 21, 2026 · UTC

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

Read original source ↗ Open in workspace

recordType

paper

region

Global