An Exact Junction-Tree Extended Formulation for Optimal Classification Trees Jiancheng Tu
arXiv:2609.24741v1 [cs.LG] 21 Sep 2026
Department of Computing, The Hong Kong Polytechnic University [email protected]
Wenqi Fan Department of Computing, The Hong Kong Polytechnic University Department of Management and Marketing, The Hong Kong Polytechnic University [email protected]
Abstract 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. Both methods solve common subtree problems that, once the preceding tree decisions are fixed, can be evaluated independently and in parallel. Computational experiments show that the exact reductions substantially reduce the size of the junction-tree formulation. The resulting linear programming formulation certifies instances for which the tested mixed-integer formulation does not establish optimality within the same computational budget, while the column-generation and message-passing methods certify more instances and achieve an order-of-magnitude reduction in geometric-mean runtime relative to an existing state-of-the-art exact method for optimal classification trees.
Keywords: optimal classification trees; extended formulations; junction trees
1
Introduction
Classification trees are widely used when predictive performance must be combined with interpretable decision rules. Classical methods such as classification and regression trees (CART) construct a tree greedily, choosing each split according to its immediate improvement (Breiman et al., 1984). Because an upstream split determines the observations available to all downstream decisions, such local choices need not produce the best tree under a prescribed global objective. Optimizing the tree jointly avoids this limitation, but constructing an optimal binary decision tree is NP-hard (Hyafil and Rivest, 1976). Exact optimization methods for classification trees must address two related issues. First, they must represent globally compatible splitting, prediction, and stopping decisions. Second, they must exploit enough structure in that representation to search or coordinate the resulting decision space efficiently and to certify optimality. Existing work approaches these issues through mathematical and constraint-based formulations, as well as through dynamic programming and exact search. For a broader review of optimization models for classification and regression trees, see Carrizosa et al. (2021).
1
1.1
Optimal Classification Trees
Mixed-integer optimization provides a general framework for jointly choosing splits, routing observations, and assigning predictions in classification trees. Bertsimas and Dunn (2017) formulate these decisions through an explicit tree template with observation-to-leaf assignments, while Verwer and Zhang (2019) develop a binary linear formulation that reduces the dependence on the number of candidate split values. Günlük et al. (2021) exploit the structure of categorical features in an integer programming formulation. Optimal trees have also been modeled through Boolean satisfiability (SAT) and maximum satisfiability (MaxSAT) encodings (Narodytska et al., 2018; Hu et al., 2020) and through constraint programming (Verhaeghe et al., 2020). Although these formulations offer considerable modeling flexibility, their computational burden grows with the number of observations and tree depth. Subsequent work has strengthened these formulations and developed decomposition methods. Aghaei et al. (2025) introduce a flow-based formulation with a stronger linear programming (LP) relaxation and exploit its structure through Benders decomposition. Alès et al. (2024); Alston et al. (2026) develop alternative flow-, cut-based, and compact formulations. Michini and Zhou (2024) study the polyhedral structure of realizable routings for multivariate trees and derive inequalities that strengthen the corresponding mixed-integer formulations. For depth-two trees, Organ et al. (2026) derive a formulation whose LP relaxation describes the convex hull of feasible trees. Path-based formulations provide a different representation and naturally lead to column generation (Firat et al., 2020; Patel et al., 2024; Subramanian and Sun, 2023). Firat et al. (2020) represent root-to-leaf decision paths as columns of an integer master formulation and generate promising paths through pricing. Patel et al. (2024) strengthen this approach through improved pricing, preprocessing, and additional valid inequalities. Subramanian and Sun (2023) develop a path-based formulation for constrained multiway-split decision trees and use column generation to handle the large path space. A limitation of these approaches is that column generation solves only the LP relaxation of the underlying integer path formulation, so convergence does not by itself certify optimality for the original tree problem. Specialized dynamic-programming and exact-search methods have substantially improved the scalability of optimal decision-tree optimization relative to general-purpose solver-based formulations (Aglin et al., 2020; Demirović et al., 2022; van der Linden et al., 2023). DL8.5 (Aglin et al., 2020), MurTree (Demirović et al., 2022), and STreeD (van der Linden et al., 2023) exploit subtree decomposability, caching, and problem-specific bounds to reuse equivalent subproblems. Optimal sparse decision trees (OSDT) and generalized and scalable optimal sparse decision trees (GOSDT) (Hu et al., 2019; Lin et al., 2020) instead organize the search around sparse-tree representations and specialized lower bounds, while Branches (Chaouki et al., 2025) uses an AND/OR graph representation to structure the search. Their scalability, however, remains limited by the combinatorial growth of the state and search spaces: worst-case complexity grows exponentially with tree size and the number of candidate binary features, so performance can deteriorate rapidly for deeper trees or high-dimensional feature sets. Related exact methods such as Quant-BnB (Mazumder et al., 2022) and ConTree (Brita et al., 2025) extend branch-and-bound and dynamic-programming ideas to continuous features.
1.2
Discussion
The preceding literature offers complementary ways to exploit tree structure. Path-based column generation searches a large path space through the LP relaxation of an integer formulation. Recursive exact-search methods use subtree decomposability, cached states, and bounds to avoid repeated search. The integral shallow formulations of Organ et al. (2026) provide a polyhedral starting point. We seek an exact LP representation for general prescribed depth that also allows smaller subtrees to be optimized and combined recursively. Our approach draws on junction-tree theory to connect subtree optimization with an exact LP representation (Wainwright and Jordan, 2008; Kolman and Koutecký, 2015), and on the relationship between dynamic 2
programming and linear optimization (Martin et al., 1990). The same decomposition supports recursive evaluation by message passing (Kschischang et al., 2001; Wainwright and Jordan, 2008). For optimal classification trees, the central modeling issue is that earlier splits determine which observations reach a subtree and which subsequent decisions are feasible. We represent these dependencies in an LP that allows subtrees to be optimized separately and their solutions combined into a feasible classification tree. This provides the basis for reducing the model and organizing the computation around subtree optimization.
1.3
Proposed Approach and Contributions
Our approach combines an exact LP representation of classification trees with algorithms that optimize and combine smaller subtrees. We make three contributions. First, we give an exact LP formulation for classification trees of any prescribed maximum depth with binary features. The model accommodates early stopping and restrictions such as minimum leaf support. We establish a convex-hull representation from which an optimal tree can be recovered by solving the LP. Its variables and constraints describe tree decisions, without introducing a separate set for each training observation. The data enter through the costs and feasibility of the split and prediction choices. Second, we derive exact reductions that make the formulation smaller. They merge choices with the same effect on the rest of the tree, optimize subtrees separately once the preceding decisions are fixed, and eliminate variables whose contributions can be incorporated into the remaining model. These operations preserve the optimal value and recovery of an optimal tree. They reduce both the number of explicit choices and the coordination needed to combine subtree decisions. Third, we develop two exact solution methods for the reduced model. Junction-tree column generation (JT-CG) solves a sequence of smaller LPs, adding promising combinations of tree decisions and using bounds over all feasible trees to certify optimality. The restricted LPs remain integral. Junction-tree message passing (JT-MP) optimizes and combines subtrees recursively to recover an optimal tree. Both methods solve the same subtree problems, which can be evaluated independently and in parallel once the preceding tree decisions are fixed. Experiments show gains in runtime relative to the tested mixed-integer programming and exact-search methods. The remainder of the paper develops the junction-tree formulation and its polyhedral properties in Section 2, the exact reductions in Section 3, and the solution methods in Section 4. Section 5 reports the computational study, and Section 6 concludes.
2
Junction-Tree Formulation
We first specify the bounded-depth optimal classification tree (OCT) model and then construct a junction-tree configuration formulation whose polyhedral properties are developed below.
2.1
Problem Setup
We consider training observations with binary features. Let 𝐼 = {1, . . . , 𝑛} index the observations, let F = {1, . . . , 𝐹} index the available features, and let K be the set of class labels, with 𝐾 = |K |. Observation 𝑖 ∈ 𝐼 has feature vector 𝑧𝑖 ∈ {0, 1} 𝐹 and label 𝑦 𝑖 ∈ K. For a prescribed maximum depth 𝐷 ≥ 1, we use the complete binary-tree template 𝐷−1 Ø B= {0, 1} ℎ , L = {0, 1} 𝐷 . (1) ℎ=0
A binary string identifies a position in the template: 𝜖 denotes the root, and appending 0 or 1 gives the left or right child. The sets B and L contain the potential internal and terminal positions, respectively. Figure 1(a) 3
illustrates this notation for 𝐷 = 3. For example, the children of position 0 are 00 and 01, and the terminal children of 00 are 000 and 001. A classification tree assigns an action 𝑇𝑣 to every position 𝑣 ∈ B ∪ L. At an internal position, the action is either a split split( 𝑓 ) on some feature 𝑓 ∈ F , a prediction predict(𝑘) of some class 𝑘 ∈ K, or the inactive action ⊥; at a terminal position, the action is a prediction or ⊥. The root is active, and a child is active if and only if its parent splits. Hence a prediction terminates its branch and makes all descendants inactive. The action ⊥ marks positions of the complete template that do not belong to the selected tree. The edge labels in Figure 1(a) describe observation routing. If position 𝑣 splits on feature 𝑓 , observation 𝑖 follows the edge labeled 0 when 𝑧 𝑖 𝑓 = 0 and the edge labeled 1 when 𝑧𝑖 𝑓 = 1. Thus, the actions along a root-to-leaf path determine both the selected tree and the observations reaching each prediction leaf. Early stopping is represented by placing a prediction at an internal position and assigning ⊥ to its descendants. (a) Classification-tree template, 𝐷 = 3 𝜖
0 0
0
1
1
1
0
00
01
1
10
11
0
1
0
1
0
1
0
1
000
001
010
011
100
101
110
111
The highlighted paths are associated with clusters 𝐶00 and 𝐶01 .
(b) Junction-tree representation 𝑆 = { 𝜖 , 0} 𝐶00 { 𝜖 , 0, 00, 000, 001}
𝑆 = { 𝜖 , 1}
𝑆 = {𝜖 } 𝐶01 { 𝜖 , 0, 01, 010, 011}
𝐶10 { 𝜖 , 1, 10, 100, 101}
𝐶11 { 𝜖 , 1, 11, 110, 111}
Figure 1: Depth-three classification-tree template and its junction-tree representation. Panel (a) shows the binary-string position labels and the 0–1 routing convention. Panel (b) groups each sibling terminal pair with its complete ancestor path. The intersections displayed above the edges are the separators of the junction tree. Let 𝐵(𝑇) denote the split nodes of 𝑇 and 𝐿 (𝑇) its prediction leaves. At a split node 𝑣, let 𝑓𝑣 denote the selected feature. Each observation follows the induced root-to-leaf path, and 𝑇 (𝑧𝑖 ) denotes its predicted class. We consider the objective ∑︁ 1 ∑︁ 𝐽 (𝑇) = 1{𝑇 (𝑧𝑖 ) ≠ 𝑦 𝑖 } + 𝜆 𝑣, 𝑓𝑣 , 𝜆 𝑣, 𝑓 ≥ 0. (2) 𝑛 𝑖∈𝐼 𝑣 ∈ 𝐵(𝑇 )
The first term is the training misclassification rate and the second penalizes split decisions. A uniform split penalty gives 𝜆|𝐵(𝑇)|, as in standard OCT regularization (Bertsimas and Dunn, 2017; Aghaei et al., 2025). When 𝜆 = 0, minimizing (2) is equivalent to maximizing training accuracy. Let T denote the set of admissible trees satisfying the structural rules above and any prescribed path or leaf requirements. For each position 𝑣, let 𝐴𝑣 denote its strict ancestors. We assume that feasibility is determined by the parent–child rules and by predicates depending only on (𝑇𝑢 : 𝑢 ∈ 𝐴𝑣 ∪ {𝑣}) and the fixed training data. This setting includes path restrictions such as prohibiting repeated features and leaf requirements such as minimum support. Constraints coupling decisions in different branches require an augmented state representation. The optimal classification tree problem is OPT𝐷 = min{𝐽 (𝑇) : 𝑇 ∈ T }. 4
(3)
2.2
Junction-Tree Construction
We now group overlapping subsets of the template into the junction-tree clusters illustrated in Figure 1(b). Definition 1 (Junction tree; Wainwright and Jordan, 2008). Let {𝐶𝑞 : 𝑞 ∈ Q} be a family of sets, called clusters. A tree J = (Q, 𝐸) is a junction tree if, for every template position 𝑣 contained in at least one cluster, the set {𝑞 ∈ Q : 𝑣 ∈ 𝐶𝑞 } induces a connected subtree of J . For an edge 𝑒 = {𝑞, 𝑟 } ∈ 𝐸, the intersection 𝑆 𝑒 = 𝐶𝑞 ∩ 𝐶𝑟 is its separator. The connectedness condition is the running-intersection property: if two clusters contain the same template position, every cluster on the path between them in J also contains that position. Let Q = {0, 1} 𝐷−1 be the set of parents of the terminal positions. For each 𝑞 ∈ Q, define
𝐶𝑞 = {𝑞0, 𝑞1} ∪ {𝑢 : 𝑢 is a strict ancestor of 𝑞} ∪ {𝑞}.
(4)
Thus, 𝐶𝑞 contains the sibling terminal positions 𝑞0 and 𝑞1 together with their complete ancestor paths. The cluster family is fixed by the complete template and does not depend on the selected tree. If a branch terminates before depth 𝐷, positions below the prediction remain in the cluster but receive the inactive action ⊥. A convenient junction tree for this cluster family is obtained by ordering Q lexicographically and connecting consecutive clusters. We denote the resulting chain by J . Its edges describe overlaps between clusters; they are not parent–child edges of the classification tree. For 𝐷 = 3, Q = {00, 01, 10, 11}, 𝐶00 − 𝐶01 − 𝐶10 − 𝐶11 . For example, so Similarly, as shown in Figure 1(b).
𝐶00 = {𝜖, 0, 00, 000, 001},
𝐶01 = {𝜖, 0, 01, 010, 011},
𝐶00 ∩ 𝐶01 = {𝜖, 0}. 𝐶10 ∩ 𝐶11 = {𝜖, 1},
𝐶01 ∩ 𝐶10 = {𝜖 },
Proposition 1 (Validity of the cluster chain). The chain J constructed above satisfies the running-intersection property and hence is a junction tree for the cluster family {𝐶𝑞 : 𝑞 ∈ Q}. For any internal position, the clusters containing it form a consecutive lexicographic interval; terminal positions each occur in a single cluster. This establishes running intersection, as detailed in Electronic Companion EC.1.1. We can now specify the decisions carried by each cluster.
5
Definition 2 (Local configuration). A local configuration on cluster 𝐶𝑞 assigns an action to every position in 𝐶𝑞 . Internal positions may split, predict, or be inactive, whereas the two terminal positions 𝑞0 and 𝑞1 may predict or be inactive. A configuration is admissible if its actions satisfy the structural rules and the ancestor-local feasibility requirements at all positions in 𝐶𝑞 . The finite set of admissible configurations for cluster 𝑞 is denoted by Ω𝑞 . Because 𝐶𝑞 contains the complete ancestor paths of its terminal positions, all ancestor-local requirements within the cluster can be evaluated from the configuration itself. For example, a configuration in Ω00 may split at 𝜖, 0, and 00 and predict at 000 and 001. A prediction at 00 makes 000 and 001 inactive, while a prediction at 0 makes 00, 000, and 001 inactive. For an edge 𝑒 = {𝑞, 𝑟 } ∈ 𝐸, configurations on 𝐶𝑞 and 𝐶𝑟 are consistent if they assign the same action to every position in 𝑆 𝑒 . Thus, in the depth-three example, configurations on 𝐶00 and 𝐶01 must agree jointly on the actions at {𝜖, 0}. These separator agreements become the coupling constraints of the formulation below.
2.3
Configuration Formulation
The formulation selects one local configuration for each cluster and coordinates neighboring clusters through their separator assignments. Training loss and split penalties enter through local configuration costs. A template position can appear in several clusters. Let 𝑚 𝑣 = {𝑞 ∈ Q : 𝑣 ∈ 𝐶𝑞 } be the number of clusters containing position 𝑣. For the construction above, 𝑚 𝑣 = 2𝐷−1− |𝑣 | for an internal position 𝑣, and 𝑚 𝑣 = 1 for a terminal position, where |𝑣| denotes the depth of 𝑣. We divide the cost incurred at position 𝑣 equally among these 𝑚 𝑣 clusters. Because each cluster contains the complete ancestor path of every position it contains, a configuration 𝜔 ∈ Ω𝑞 determines which observations reach each position in 𝐶𝑞 . Define 𝜆 𝑣, 𝑓 , ∑︁ 1 1{𝑦 𝑖 ≠ 𝑘 }, ℓ𝑣 (𝜔) = 𝑛 𝑖 ∈ 𝐼: 𝑖 reaches 𝑣 under 𝜔 0,
𝜔 𝑣 = split( 𝑓 ), 𝜔 𝑣 = predict(𝑘),
(5)
𝜔 𝑣 = ⊥.
The local configuration cost is 𝑐 𝑞 (𝜔) =
∑︁ ℓ𝑣 (𝜔) 𝑣 ∈𝐶𝑞
𝑞 ∈ Q,
,
𝑚𝑣
𝜔 ∈ Ω𝑞 .
(6)
For the depth-three example, the root cost is divided among four clusters, whereas the cost at position 0 is divided between 𝐶00 and 𝐶01 . A terminal prediction cost is assigned to its unique cluster. Proposition 2 (Cost decomposition). For every 𝑇 ∈ T , ∑︁ 𝐽 (𝑇) = 𝑐 𝑞 (𝑇 | 𝐶𝑞 ). 𝑞∈ Q
6
(7)
The identity follows because the cost at each position 𝑣 is divided among exactly the 𝑚 𝑣 clusters containing that position. A proof is given in Electronic Companion EC.1. For every 𝑞 ∈ Q and 𝜔 ∈ Ω𝑞 , let 𝑥 𝑞 𝜔 = 1 if configuration 𝜔 is selected in cluster 𝑞, and let it be zero otherwise. For an edge 𝑒 = {𝑞, 𝑟 } ∈ 𝐸, let Σ𝑒 be the set of separator assignments occurring in a configuration of either endpoint, and write 𝜔| 𝑆𝑒 for the restriction of 𝜔 to 𝑆 𝑒 . The junction-tree integer programming formulation is ∑︁ ∑︁ min 𝑐 𝑞 (𝜔)𝑥 𝑞 𝜔 , (8a) s.t.
𝑞 ∈ Q 𝜔 ∈Ω𝑞
∑︁
𝑥𝑞 𝜔 = 1
𝜔 ∈Ω𝑞
∑︁
𝜔 ∈Ω𝑞 : 𝜔 | 𝑆𝑒 =𝜎
𝑥𝑞 𝜔 −
𝑥 𝑞 𝜔 ∈ {0, 1}
∑︁
𝑥𝑟 𝜔 = 0
𝜔 ∈Ω𝑟 : 𝜔 | 𝑆𝑒 =𝜎
𝑞 ∈ Q,
(8b)
𝑒 = {𝑞, 𝑟 } ∈ 𝐸, 𝜎 ∈ Σ𝑒 ,
(8c)
𝑞 ∈ Q, 𝜔 ∈ Ω𝑞 .
(8d)
Constraint (8b) selects one configuration in each cluster. Constraint (8c) matches complete separator assignments between neighboring clusters. For a feasible tree 𝑇 ∈ T , define its configuration-selection vector by 𝑥 𝑞𝑇 𝜔 = 1{𝑇 | 𝐶𝑞 = 𝜔}. (9)
We refer to (8) as the junction-tree integer program (JT-IP). Its LP relaxation, the junction-tree LP (JT-LP), replaces (8d) with 𝑥 𝑞 𝜔 ≥ 0; let 𝑃 denote the resulting feasible region.
2.4
Polyhedral Properties
JT-LP is a configuration formulation on a valid junction tree. Classical junction-tree consistency (Wainwright and Jordan, 2008, Proposition 2.1) and bounded-treewidth configuration results (Kolman and Koutecký, 2015, Lemma 2.1 and Theorem 1.1) provide the generic integrality mechanism. The OCT construction above specifies the local actions, clusters, separator assignments, and costs to which these results are applied. The remaining question is whether consistency of these local actions enforces all OCT requirements. Complete ancestor paths ensure that each routing and feasibility condition is checked with the same information in every cluster containing it. The next theorem combines this correspondence with junction-tree consistency; Proposition 2 then transfers the polyhedral result to the OCT objective. Theorem 1 (Convex-hull representation). Under the ancestor-local feasibility assumptions of Section 2.1, separator-consistent local configurations are in one-to-one correspondence with the feasible template trees in T . Consequently, 𝑃 = conv{𝑥 𝑇 : 𝑇 ∈ T }. (10)
Hence every extreme point of JT-LP is integral. If T ≠ ∅, JT-IP and JT-LP have optimal value OPT𝐷 , and an optimal classification tree can be recovered from an optimal JT-LP solution.
Electronic Companion EC.1 proves the configuration–tree correspondence and (10). The constructive proof also gives a procedure for recovering an optimal tree from an optimal LP solution. Fixing excluded nonnegative configuration variables to zero defines a face of 𝑃. This observation matters when the full configuration domain is too large to enumerate: retaining a compatible subset of configurations preserves integrality even though it can exclude the globally optimal tree. The next corollary establishes the feasible-tree interpretation of the restricted masters used by column generation. 7
Remark 1 (Shallow configuration models). For 𝐷 = 2, the formulation reduces to the configuration structure of Organ et al. (2026) under matched feature, loss, and feasibility assumptions. Under the corresponding depth-three assumptions, the four-group formulation in Appendix A of the 2023 preprint of Organ et al. (2026) has the same normalization and joint-ancestor consistency structure. Electronic Companion EC.1 gives the detailed variable mapping. The construction above extends this configuration principle to arbitrary prescribed depth with early stopping and ancestor-local feasibility. b 𝑞 ⊆ Ω𝑞 , restrict JT-LP to the variables Corollary 1 (Restricted-master integrality). For arbitrary subsets Ω b associated with Ω𝑞 and retain every separator equation (8c) whose assignment occurs in a retained configuration at either endpoint. After extending each restricted vector by zeros on all excluded coordinates, the resulting feasible region is either empty or n o b 𝑞 for every 𝑞 ∈ Q . conv 𝑥 𝑇 : 𝑇 ∈ T , 𝑇 | 𝐶𝑞 ∈ Ω Consequently, every nonempty restricted master has only integral extreme points and an integral optimum for every linear objective. A feasible restricted master therefore yields a feasible classification tree and an upper bound on OPT𝐷 . Certification for the full problem requires the pricing or lower-bound tests developed in Section 4.3. Remark 2 (Extensions of the model). Any objective that is additive in fixed prediction and split costs changes only 𝑐 𝑞 (𝜔) and leaves the feasible region and Theorem 1 unchanged. For example, balanced misclassification loss is obtained by replacing the weight 1/𝑛 in (5) with 1/(|K |𝑛 𝑦𝑖 ), where 𝑛 𝑘 > 0 is the number of observations in class 𝑘. The construction also extends to multiway classification trees on a fixed bounded-depth template. Each split rule specifies a partition of the observations among its branches. When costs remain additive and feasibility is determined by a decision and its ancestors, the same consistency and tree-recovery arguments apply after adapting the local configurations to the multiway template. The formulation sizes depend on the branching structure. Each cluster contains 𝐷 + 2 template positions, so the induced tree decomposition has width at most 𝐷 + 1. With explicit prediction labels, no feasibility filtering, and early stopping allowed, the unfiltered Í number of configurations per cluster is 𝐹 𝐷 𝐾 2 + 𝐾 𝐷−1 𝐹 𝑗 . Since there are 2𝐷−1 clusters, the corresponding 𝑗=0 Í 𝑗 . total number of configuration variables is 2𝐷−1 𝐹 𝐷 𝐾 2 + 𝐾 𝐷−1 𝐹 𝑗=0 For comparison, consider the full-depth split-only representation in which every internal position splits and terminal predictions are optimized independently rather than indexed as configuration actions. In this case the displayed formulation has 2𝐷−1 𝐹 𝐷 , | {z } columns
2𝐷−1 + |
𝐷−1 ∑︁
2ℎ−1 𝐹 ℎ ,
(11)
ℎ=1
{z
equalities
}
before redundant rows are removed. The master contains no observation-indexed variables or constraints, although its local costs and feasibility filters depend on the training data. The configuration space nevertheless grows exponentially with the prescribed depth. This growth motivates the exact reductions developed in Section 3.
3
Exact Reductions
All three reductions use the same principle: once the assignments on the relevant separators are fixed, decisions that are not visible outside those separators can be optimized locally. Separator-signature compression applies 8
this principle within a cluster, subtree contraction applies it to a block of clusters, and endpoint elimination removes a leaf cluster after transferring its conditional cost to its neighbor. For the fixed additive objective (2), each operation preserves the optimal value and retains enough information to recover an optimal tree. Proofs are given in Electronic Companion EC.2.
3.1
Signature Compression
For a cluster 𝑞 ∈ Q, let 𝑁 J (𝑞) denote its neighbors in J . The separator signature of a configuration 𝜔 ∈ Ω𝑞 is 𝛾𝑞 (𝜔) = 𝜔| 𝑆𝑒 : 𝑒 = {𝑞, 𝑟 } ∈ 𝐸, 𝑟 ∈ 𝑁 J (𝑞) , (12) and let
Γ𝑞 = {𝛾𝑞 (𝜔) : 𝜔 ∈ Ω𝑞 }
be the signatures induced by admissible configurations. For 𝜂 ∈ Γ𝑞 , define
𝑐¯𝑞 (𝜂) = min{𝑐 𝑞 (𝜔) : 𝜔 ∈ Ω𝑞 , 𝛾𝑞 (𝜔) = 𝜂}.
(13)
For tree recovery, one minimizing configuration is stored for each signature. Since admissibility is already encoded in Ω𝑞 , this minimization removes only distinctions that are invisible on every incident separator. Introduce one variable 𝑦 𝑞 𝜂 for each signature. The compressed LP has the same normalization and separator-consistency structure as JT-LP: ∑︁ ∑︁ min 𝑐¯𝑞 (𝜂)𝑦 𝑞 𝜂 , (14a) s.t.
𝑞 ∈ Q 𝜂 ∈Γ𝑞
∑︁
𝑦𝑞 𝜂 = 1
𝜂 ∈Γ𝑞
∑︁
𝜂 ∈Γ𝑞 :𝜂𝑒 =𝜎
𝑦𝑞 𝜂 ≥ 0
𝑦𝑞 𝜂 −
∑︁ 𝜂 ′ ∈Γ𝑟 :𝜂𝑒′ =𝜎
𝑦𝑟 𝜂′ = 0
𝑞 ∈ Q,
(14b)
𝑒 = {𝑞, 𝑟 } ∈ 𝐸, 𝜎 ∈ Σ𝑒 ,
(14c)
𝑞 ∈ Q, 𝜂 ∈ Γ𝑞 .
(14d)
Here 𝜂𝑒 denotes the assignment induced by signature 𝜂 on separator 𝑆 𝑒 . Configurations with the same signature have identical coefficients in every master constraint. Their costs can therefore be minimized within the signature class. The proposition below formalizes both directions of this reduction: aggregation gives a feasible compressed vector, and the stored representatives lift a compressed solution back to JT-LP. Proposition 3 (Exact signature compression). Let 𝑃 be the JT-LP feasible region and define ∑︁ 𝑦𝑞 𝜂 = 𝑥𝑞 𝜔 .
(15)
𝜔 ∈Ω𝑞 : 𝛾𝑞 ( 𝜔)=𝜂
The feasible region of (14) is the image of 𝑃 under (15). The original and compressed LPs have the same optimal value, the compressed feasible region is integral, and an optimal tree can be recovered from the stored minimizing configurations. For the specified objective, compression retains a minimum-cost representative of each signature class. Its coefficients preserve the interface, and its stored configuration supplies tree recovery. A change of objective can change the minimizing representative. Under the complete split-only counting convention of (11), with terminal predictions optimized locally, each cluster has 𝐹 𝐷 configurations. The deepest internal decision is private, whereas the remaining 𝐷 − 1 split decisions determine the incident separator assignments. Hence 2𝐷−1 𝐹 𝐷
−→
2𝐷−1 𝐹 𝐷−1 .
(16)
For the general model, early stopping and feasibility filters are already reflected in the admissible sets Ω𝑞 . 9
3.2
Subtree Contraction
Signature compression optimizes decisions private to one cluster. Larger reductions become possible when adjacent clusters are grouped, because their internal separators no longer connect the group to the rest of the model. Subtree contraction applies the same conditional minimization to such a group. Its boundary must still retain the ancestor decisions that determine routing and feasibility within the private subtree. Fix a private depth ℎ ∈ {1, . . . , 𝐷} and let Q ℎ = {0, 1} 𝐷−ℎ index the roots of the corresponding private subtrees. For 𝑡 ∈ Q ℎ , let B𝑡 = {𝑞 ∈ Q : 𝑞 has prefix 𝑡} be the consecutive block of original clusters associated with the depth-ℎ subtree rooted at 𝑡. Grouping the clusters in each B𝑡 produces a smaller lexicographic junction-tree chain. A separator assignment 𝜎 for the grouped block fixes the ancestor decisions visible outside the private subtree and therefore fixes the observations reaching 𝑡 and the inherited feasibility restrictions. Let Ξ𝑡 be the set of such assignments that admit at least one feasible completion. For 𝜎 ∈ Ξ𝑡 , let 𝑉ℎ (𝑡, 𝜎) denote the minimum prediction loss and split penalties contributed by a feasible depth-ℎ subtree rooted at 𝑡. The cost of the corresponding contracted state is 𝜅 𝑡 (𝜎) =
∑︁ 𝑣 strict ancestor of 𝑡
ℓ𝑣 (𝜎) + 𝑉ℎ (𝑡, 𝜎). 𝐷−ℎ− |𝑣 | 2
(17)
The first term is the portion of the shared-ancestor costs allocated to the block by (6). Prediction losses retain the full-sample denominator 𝑛. If an ancestor prediction makes the private subtree inactive, then 𝑉ℎ (𝑡, 𝜎) = 0. The contracted master replaces each block B𝑡 by one state for each 𝜎 ∈ Ξ𝑡 , with cost 𝜅 𝑡 (𝜎), one normalization equation per block, and the separator-consistency equations induced between adjacent blocks. Proposition 4 (Contraction as compression). Under the assumptions of Theorem 1, for every 𝑡 ∈ Q ℎ and 𝜎 ∈ Ξ𝑡 , ∑︁ (𝜔𝑞 )𝑞 ∈ B𝑡 are mutually consistent 𝜅 𝑡 (𝜎) = min 𝑐 𝑞 (𝜔𝑞 ) : , (18) and agree with 𝜎 on the external separators 𝑞 ∈ B𝑡 with value +∞ if no feasible completion exists. Thus subtree contraction is equivalent to grouping the block and then applying signature compression with respect to its external separator assignments. For ℎ = 1, the operation reduces to signature compression on the original clusters. Proposition 4 identifies the contracted cost with the minimum cost of a compatible block in the original formulation. The next result uses this identity to establish global optimality and tree recovery. Replacing a private completion by its minimizer leaves every external separator assignment unchanged, so the replacements can be made independently across blocks. Proposition 5 (Exact subtree contraction). Assume the ancestor-local feasibility conditions of Section 2.1, the additive objective (2), and T ≠ ∅. The contracted master has optimal value OPT𝐷 and an integral optimum. An optimal full classification tree can be recovered by combining an optimal set of contracted states with the stored minimizing private subtrees. After contraction, another application of signature compression with the same external separators produces no additional merging. Eliminating separator information can, however, create new signature equivalences. Section 4.1 gives the dynamic program used to compute 𝑉ℎ (𝑡, 𝜎). 10
3.3
Endpoint Elimination
Compression and contraction reduce the states within each retained group. Endpoint elimination reduces the number of groups. A leaf cluster interacts with the rest of the junction tree through a single separator; its optimized conditional cost can therefore be added to its neighbor. Unlike compression, this operation also removes the corresponding consistency equations. Let 𝑞 be a leaf of the compressed junction tree, let 𝑟 be its unique neighbor, and write 𝑒 = {𝑞, 𝑟 }. Since 𝑞 has only one incident separator, its signature is identified with an assignment on 𝑆 𝑒 . First remove any state of 𝑟 whose separator assignment has no feasible extension in 𝑞. For every remaining state 𝜂 ∈ Γ𝑟 , update its cost by e 𝑐𝑟 (𝜂) = 𝑐¯𝑟 (𝜂) + 𝑐¯𝑞 (𝜂𝑒 ). (19) Proposition 6 (Exact endpoint elimination). After the update (19), deleting cluster 𝑞, its normalization equation, and the separator equations on 𝑒 preserves the optimal value and integrality. The deleted variables are recovered from ∑︁ 𝑦𝑞 𝜎 = 𝑦𝑟 𝜂 , 𝜎 ∈ Γ𝑞 . (20) 𝜂 ∈Γ𝑟 :𝜂𝑒 =𝜎
Combining the recovered signatures with the stored representatives from Proposition 3 recovers an optimal tree. Corollary 2 (Repeated elimination). Any sequence of endpoint eliminations, recompressing each newly exposed leaf with respect to its remaining separator, preserves the optimal value, integrality, and recovery of an optimal tree. Stopping before all clusters are eliminated leaves a smaller exact LP. Eliminating all nonroot clusters gives the min-sum recursion developed in Section 4.2. The depth-three case illustrates the size reduction. Consider the complete split-only model with 𝐹 candidate rules at each split and terminal predictions optimized locally, before feasibility filtering. Optimizing the deepest splits reduces the explicit variable count from 4𝐹 3 to 4𝐹 2 . Endpoint elimination then leaves 2𝐹 2 variables: 4𝐹 3 −→ 4𝐹 2 −→ 2𝐹 2 .
The remaining model coordinates the two sides of the tree through the root split and has 𝐹 + 1 linearly independent equalities. Thus, for 𝐹 = 100, the variable count falls from four million to twenty thousand. Electronic Companion EC.2 derives these counts. These reductions decrease the size of the explicit LP; its coefficients are obtained by optimizing the eliminated subtree decisions. This separates subtree evaluation from the coordination needed to form a complete tree. Eliminating the remaining decisions conditional on the root gives the message-passing method in Section 4. The reductions above require the separator assignments to contain all information through which an eliminated configuration or block interacts with the rest of the model. If additional coupling is introduced, the separator state must be augmented accordingly.
4
Exact Solution Methods
JT-MP and JT-CG share the same subtree evaluator but combine its results through message passing and column generation, respectively. Both recover feasible trees and use lower bounds valid for the original OCT problem to certify optimality. These bounds can incorporate results from unfinished subtree searches.
11
4.1
Conditional Subtree Evaluation
Subtree contraction removes private decisions from the explicit formulation, but their conditional costs must still be computed. At an active position 𝑣, let a state 𝑠 contain the observations reaching 𝑣 together with the inherited decisions needed to evaluate ancestor-local feasibility. Let 𝐿 (𝑣, 𝑠) be the minimum feasible prediction loss at 𝑣, with value +∞ when prediction is not allowed, and let F (𝑣, 𝑠) be the admissible split 𝑓 features. If feature 𝑓 is selected, let 𝑠 𝑏 be the child state on branch 𝑏 ∈ {0, 1} after routing the observations and updating the inherited decisions. For a contracted block of private depth ℎ, let 𝑑 denote the remaining depth at the current position: 𝑑 = ℎ at the block root and 𝑑 = ℎ − 𝑗 after 𝑗 successive splits. Define the depth-zero value and, for 𝑑 = 1, . . . , ℎ, the recurrence 𝑉0 (𝑣, 𝑠) = 𝐿 (𝑣, 𝑠), 𝑉𝑑 (𝑣, 𝑠) = min 𝐿 (𝑣, 𝑠),
h
𝑓 𝑓 min 𝜆 𝑣, 𝑓 + 𝑉𝑑−1 (𝑣0, 𝑠0 ) + 𝑉𝑑−1 (𝑣1, 𝑠1 ) 𝑓 ∈ F (𝑣,𝑠)
(21)
i .
Only feasible actions are included in the minima. An inactive subtree has value zero, and prediction losses retain the full-sample denominator 𝑛. For a contracted block rooted at 𝑡, the separator assignment 𝜎 induces an initial state 𝑠 in (21). The notation 𝑉ℎ (𝑡, 𝜎) from Section 3.2 denotes 𝑉ℎ (𝑡, 𝑠) evaluated at this induced state. Minimizing actions are stored for tree recovery. Algorithm 1 evaluates (21) for any prescribed private depth ℎ ≥ 0 by combining conditional costs from the leaves to the root and recording minimizing choices. For the algorithm, write 𝑥 = (𝑣, 𝑠), 𝐿 (𝑥) = 𝐿 (𝑣, 𝑠), 𝑓 𝑓 and 𝑥 𝑏 = (𝑣𝑏, 𝑠 𝑏 ). Let S 𝑗 contain the conditional states reached from the input by 𝑗 successive admissible splits, for 𝑗 = 0, . . . , ℎ, so every state in S 𝑗 has remaining depth 𝑑 = ℎ − 𝑗. States are identified by the full remaining subproblem, including inherited feasibility restrictions and position-dependent costs. These sets specify dependencies and need not be stored simultaneously. Algorithm 1 Exact conditional-subtree evaluation 1 2 3 4 5 6 7 8 9 10 11 12
Input: Subtree root 𝑡, separator assignment 𝜎 with induced state 𝑠, and private depth ℎ ≥ 0. Output: Exact private cost 𝑉ℎ (𝑡, 𝜎) and a minimizing subtree, or infeasibility. If the ancestors make 𝑡 inactive, return cost 0 and an inactive subtree. Otherwise set 𝑥 in = (𝑡, 𝑠) and S0 = {𝑥in }. 𝑓 For 𝑗 = 0, . . . , ℎ − 1, generate S 𝑗+1 from 𝑥 𝑏 for 𝑥 = (𝑢, 𝑠′ ) ∈ S 𝑗 , 𝑓 ∈ F (𝑢, 𝑠′ ), and 𝑏 ∈ {0, 1}. For each 𝑥 ∈ Sℎ , set 𝐵0 (𝑥) ← 𝐿 (𝑥); if finite, record a feasible minimizing prediction label as 𝐴0 (𝑥). For 𝑑 = 1, . . . , ℎ do Combine costs from the leaves to the root For each 𝑥 = (𝑢, 𝑠′ ) ∈ Sℎ−𝑑 do Set 𝐵 𝑑 (𝑥) ← 𝐿 (𝑥); if finite, record a feasible minimizing prediction label as 𝐴𝑑 (𝑥). For each 𝑓 ∈ F (𝑢, 𝑠′ ) do 𝑓 𝑓 Evaluate 𝑐 𝑓 = 𝜆𝑢, 𝑓 + 𝐵 𝑑−1 (𝑥0 ) + 𝐵 𝑑−1 (𝑥1 ). 𝑓 𝑓 If 𝑐 𝑓 < 𝐵 𝑑 (𝑥), set 𝐵 𝑑 (𝑥) ← 𝑐 𝑓 and record 𝑓 and pointers to 𝐴𝑑−1 (𝑥0 ) and 𝐴𝑑−1 (𝑥1 ) as 𝐴𝑑 (𝑥). If 𝐵 ℎ (𝑥 in ) = +∞, return infeasibility. Backtrack from 𝐴ℎ (𝑥 in ): a prediction ends the branch and inactivates its descendants; a split follows both stored child choices. Return 𝑉ℎ (𝑡, 𝜎) = 𝐵 ℎ (𝑥in ) and the recovered subtree.
For ℎ = 0, the split-generation and cost-combination loops are empty, so the algorithm returns the best feasible prediction or infeasibility. Prediction costs minimize over all feasible classes, retain the full-sample denominator 𝑛, and equal +∞ when prediction is infeasible. An empty split domain leaves the prediction value unchanged. Each split penalty is charged once. The allocated ancestor contribution is added to the returned private cost as in (17). Successive applications of (21) give 𝐵 𝑑 (𝑥) = 𝑉𝑑 (𝑢, 𝑠′ ) for 𝑥 = (𝑢, 𝑠′ ) ∈ Sℎ−𝑑 , and the recorded choices recover a minimizing feasible subtree. The algorithm assumes complete evaluation; a resource stop leaves an unresolved conditional cost rather than proving infeasibility. 12
The private depth ℎ controls the division of work between the explicit coordinator and the conditional evaluator. With 𝐾 = |K |, early stopping and repeated features give the unfiltered bound 𝐷−ℎ−1 ∑︁ © ª |Ξ𝑡 | ≤ 2𝐷−ℎ 𝐹 𝐷−ℎ + 𝐾 𝐹 𝑗® , 𝑗=0 𝑡 ∈ Qℎ « ¬
∑︁
(22)
where the sum is zero when 𝐷 − ℎ = 0. Path and leaf restrictions can only reduce this count. Increasing ℎ decreases the number of explicit ancestor states but enlarges each conditional subtree problem; at ℎ = 𝐷, the single conditional problem is the original OCT problem. Table 1 reports unfiltered counts for general (𝐷, ℎ) and selected depths. Original counts assume split-only configurations with locally optimized terminal labels; representative bounds allow early stopping. For fixed 𝐷, increasing ℎ reduces the group count and representative bound. The baseline uses ℎ = 1 for 𝐷 = 2, 3 and ℎ = 3 for 𝐷 = 4, 5; Section 5.4 compares alternative private depths. Table 1: Configuration and representative-state counts. 𝐷 Original columns Private depth ℎ Groups
4.2
𝐷
2𝐷−1 𝐹 𝐷
ℎ
2𝐷−ℎ
2 3 3
2𝐹 2 4𝐹 3 4𝐹 3
1 1 2
2 4 2
4 4 4
8𝐹 4 8𝐹 4 8𝐹 4
1 2 3
8 4 2
5 5 5
16𝐹 5 16𝐹 5 16𝐹 5
1 2 3
16 8 4
Representative bound 𝐷−ℎ Í 𝐹 + 𝐾 𝐷−ℎ−1 𝐹𝑗 𝑗=0
2𝐷−ℎ
2(𝐹 + 𝐾) 4[𝐹 2 + 𝐾 (𝐹 + 1)] 2(𝐹 + 𝐾)
8[𝐹 3 + 𝐾 (𝐹 2 + 𝐹 + 1)] 4[𝐹 2 + 𝐾 (𝐹 + 1)] 2(𝐹 + 𝐾)
16[𝐹 4 + 𝐾 (𝐹 3 + 𝐹 2 + 𝐹 + 1)] 8[𝐹 3 + 𝐾 (𝐹 2 + 𝐹 + 1)] 4[𝐹 2 + 𝐾 (𝐹 + 1)]
Message Passing
Complete endpoint elimination gives the standard min-sum recursion on the junction tree (Kschischang et al., 2001; Wainwright and Jordan, 2008). We first write the recursion for the original configuration formulation; after exact reduction, the same equations apply with reduced states and costs. Root J at cluster 𝑞 0 . For neighboring clusters 𝑞 and 𝑝, let 𝑆 𝑞 𝑝 = 𝐶𝑞 ∩ 𝐶 𝑝 , and let 𝑁 (𝑞) denote the neighbors of 𝑞. The message from 𝑞 to its parent 𝑝 is 𝑐 𝑀𝑞→ 𝑝 (𝜎) =
∑︁ 𝑐 min 𝑐 𝑞 (𝜔) + 𝑀𝑟→𝑞 (𝜔| 𝑆𝑟𝑞 ) . 𝜔 ∈Ω𝑞 : 𝑟 ∈ 𝑁 (𝑞)\{ 𝑝} 𝜔 | 𝑆𝑞 𝑝 =𝜎
(23)
A minimum over an empty domain is +∞. After an inward sweep, ∑︁ 𝑐 OPT𝐷 = min 𝑐 𝑞0 (𝜔) + 𝑀𝑟→𝑞0 (𝜔| 𝑆𝑟𝑞0 ) . 𝜔 ∈Ω𝑞0 𝑟 ∈ 𝑁 (𝑞0 )
(24)
A minimizing root state and the stored minimizing choices in (23) recover an optimal tree by backtracking. Separator agreement and the running-intersection property make the recovered local states globally consistent. 13
For the constructed chain, once local states, costs, and separator projections are available, a sweep requires Í Í 𝑂 ( 𝑞 |Ω𝑞 | + 𝑒 |Σ𝑒 |) arithmetic operations when projections are preindexed. This is a coordination bound; constructing states and evaluating their costs are separate tasks. Let 𝐸 (𝑞) be the edges incident to cluster 𝑞. Orient each edge 𝑒 of the junction tree and let 𝑠𝑞𝑒 ∈ {+1, −1} be its sign at 𝑞, with opposite signs at its endpoints. With 𝛼𝑞 for the normalization equation and 𝜋𝑒 𝜎 for separator assignment 𝜎, the dual of JT-LP is ∑︁ max 𝛼𝑞 s.t.
𝑞∈ Q
𝛼𝑞 +
∑︁ 𝑒∈𝐸 (𝑞)
𝑠𝑞𝑒 𝜋𝑒, 𝜔 | 𝑆𝑒 ≤ 𝑐 𝑞 (𝜔) 𝑞 ∈ Q, 𝜔 ∈ Ω𝑞 ,
(25)
with unrestricted dual variables. The message recursion also constructs dual prices for separator consistency. A message is the minimum cost of the component on one side of an edge, conditional on the separator assignment. Charging this cost at the child and subtracting it at the parent makes the local message inequalities match the dual constraints. The following proposition makes this relation explicit, including separator assignments without a feasible conditional completion. Proposition 7 (Min-sum messages and the JT-LP dual). Assume T ≠ ∅ and the nonnegative local costs in (6). Root J at 𝑞 0 and orient every edge from child 𝑞 to parent 𝑝, with sign +1 at the child. Choose 𝐻 larger 𝑐 b𝑞→ than the cost of a feasible tree. Compute finite messages 𝑀 𝑝 by (23), assigning value 𝐻 to an empty local minimization domain and using the resulting finite incoming messages in all other cases. Then 𝑐 b𝑞→ 𝜋𝑒 𝜎 = 𝑀 𝑝 (𝜎),
𝛼𝑞0 = OPT𝐷 ,
𝛼𝑞 = 0
(𝑞 ≠ 𝑞 0 )
is optimal for (25). Together with the tree obtained by backtracking, these multipliers form a primal–dual optimal pair for JT-LP. Thus complete elimination produces both an optimal tree and an LP optimality certificate. We call this method JT-MP. On a contracted representation, JT-MP applies the same recursion to the contracted states and their conditional costs. The cost-bound refinements used by the reported implementation are given in Electronic Companion EC.3.
4.3
Column Generation
JT-CG retains only a subset of the configuration columns and exposes omitted states by pricing, in the spirit of Dantzig–Wolfe decomposition (Dantzig and Wolfe, 1960). 4.3.1
Restricted Master
b 𝑞 ⊆ Ω𝑞 be the retained configurations at cluster 𝑞. The restricted master problem (RMP) is the Let Ω restriction of JT-LP described in Corollary 1: it keeps the retained columns and every separator row induced by a retained column at either endpoint. A newly added column is therefore accompanied by any separator rows that it introduces, giving simultaneous column-and-row generation (Muter et al., 2013; Spliet, 2024). Let 𝑧 𝑅 denote the RMP optimum. By Corollary 1, every feasible RMP has an integral optimum, so 𝑧 𝑅 is the value of a feasible classification tree and is an upper bound on OPT𝐷 . If an LP solver returns a fractional point on the optimal face, a tree of the same value can be recovered by the support traversal used in Theorem 1. The RMP is initialized from the restrictions of any feasible tree; subsequent column additions preserve feasibility. 14
Orient every junction-tree edge and let 𝑠𝑞𝑒 be its sign at cluster 𝑞. Denote the dual variables for the normalization and separator rows by 𝛼𝑞 and 𝜋𝑒 𝜎 . Multipliers for separator rows not present in the current RMP are set to zero. The RMP dual is obtained from (25) by retaining only the constraints corresponding to retained columns, and strong duality gives ∑︁ 𝛼𝑞 = 𝑧 𝑅 . 𝑞∈ Q
4.3.2
Pricing
For a full-domain configuration 𝜔 ∈ Ω𝑞 , define its reduced cost by ∑︁ e 𝑐 𝑞 (𝜔) = 𝑐 𝑞 (𝜔) − 𝛼𝑞 − 𝑠𝑞𝑒 𝜋𝑒, 𝜔 | 𝑆𝑒 ,
(26)
𝑒∈𝐸 (𝑞)
and let
𝑟 𝑞 = min e 𝑐 𝑞 (𝜔). 𝜔 ∈Ω𝑞
(27)
A negative value identifies a violated full-master dual constraint and a candidate column to add to the RMP. Because all configurations in one signature class have identical master coefficients, signature compression is compatible with pricing: only the minimum-cost representative of a signature need be considered. After subtree contraction, the same pricing formula applies with the contracted state set and the conditional costs 𝜅 𝑡 (𝜎) in place of the original configurations and costs. Conditional subtree costs are independent of the RMP dual multipliers and may therefore be reused across pricing iterations. 4.3.3
Certification
Corollary 1 makes the RMP objective 𝑧 𝑅 an upper bound on the full optimum. A lower bound requires accounting for configurations omitted from the RMP. Pricing measures the largest dual-constraint violation in each cluster. Subtracting these violations from the corresponding normalization prices produces a dual solution feasible for the full master, as stated next. All pricing values must refer to the same dual vector. Proposition 8 (Pricing lower bound). Let (𝛼, 𝜋) be an optimal dual solution of a feasible RMP, with absent separator multipliers set to zero. If 𝑟 𝑞 ≤ 𝑟 𝑞 is a valid lower bound on the pricing value (27) computed with this same dual vector, then ∑︁ LBCG = 𝑧 𝑅 + min{0, 𝑟 𝑞 } ≤ OPT𝐷 . (28) 𝑞∈ Q
If exact pricing gives 𝑟 𝑞 ≥ −𝜏 for every 𝑞, where 𝜏 ≥ 0, then 𝑧 𝑅 − |Q|𝜏 ≤ OPT𝐷 ≤ 𝑧 𝑅 .
(29)
In particular, nonnegative exact reduced costs certify optimality. Electronic Companion EC.3 gives the proof. The same correction applies to any RMP-dual-feasible Í vector: if 𝑧 𝐷 = 𝑞 𝛼𝑞 is its dual objective, then ∑︁ 𝑧𝐷 + min{0, 𝑟 𝑞 } (30) 𝑞∈ Q
is a valid lower bound on OPT𝐷 . 15
Algorithm 2 gives the exact-cost JT-CG scheme in the original configuration notation; contraction replaces these domains and costs as in (17). In the D4/D5 implementation, subtree searches provide valid lower bounds and feasible solutions before completion. The solver uses these bounds to select further evaluations and can certify optimality before every subtree cost is known exactly. It retains lower bounds for all candidate states and feasible subtrees for their upper costs. Newly priced columns are admitted after exact cost evaluation; initial columns induced by incumbent trees may retain upper costs. Refinement can therefore improve an existing column as well as produce a new one. The restricted master uses the current representative costs, and certification takes the strongest available full-domain pricing, lower-cost message, and depth bounds. Algorithm EC.1 in Electronic Companion EC.3 specifies how these bounds are updated and when the restricted master is solved again. A resource stop returns the best feasible tree and valid bounds. Algorithm 2 Junction-tree column generation (JT-CG)
1 2 3 4 5 6 7 8 9 10 11
Input: Configuration domains Ω𝑞 , feasible tree 𝑇 0 , absolute gap tolerance 𝜀 ≥ 0, and resource limit. Output: A feasible tree 𝑇 and bounds LB ≤ OPT𝐷 ≤ UB = 𝐽 (𝑇). b 𝑞 with the configuration induced by 𝑇 0 and add all induced separator rows. Set 𝑇 ← 𝑇 0 , Initialize each Ω UB ← 𝐽 (𝑇), and LB ← −∞. while resources remain do Solve the RMP; obtain 𝑧 𝑅 , an optimal dual vector (𝛼, 𝜋), and a tree 𝑇𝑅 from its optimal support. Set absent separator multipliers to zero. If 𝐽 (𝑇𝑅 ) < UB, set 𝑇 ← 𝑇𝑅 and UB ← 𝐽 (𝑇𝑅 ). Price every cluster over its full domain in parallel using the same dual vector; obtain negative-reduced-cost configurations and valid bounds 𝑟 𝑞 ≤ 𝑟 𝑞 . Í Update LB ← max{LB, 𝑧 𝑅 + 𝑞 ∈ Q min{0, 𝑟 𝑞 }}. Strengthen it with the configuration-cost bound and, when available, the depth bound in Electronic Companion EC.3. if UB − LB ≤ 𝜀 then return (𝑇, LB, UB). Add selected negative-reduced-cost configurations and every separator row they induce. If no column was found and pricing is incomplete, retain the current dual vector and resume unfinished pricing at Step 5 without resolving the RMP, until a column, certificate, or resource stop is obtained. If pricing is exact and 𝑟 𝑞 ≥ 0 for every 𝑞 ∈ Q, return (𝑇, UB, UB). end while; return (𝑇, LB, UB).
The pseudocode uses exact reduced-cost signs and no column deletion. Each pricing correction uses bounds from one fixed dual solution. If the resource limit interrupts a solve or pricing call, return the incumbent and the last valid bounds. With complete exact pricing and no resource limit, every nonterminal iteration adds a previously absent configuration from a finite domain, so the procedure terminates finitely.
4.4
Parallel Evaluation
For a fixed separator assignment, the conditional subtree problem in Section 4.1 depends only on the observations and feasibility information carried by that state. Distinct conditional requests can therefore be evaluated independently. Within one request, candidate split and prediction costs can also be evaluated in batches before being combined through (21). Parallel workers evaluate conditional costs. JT-MP combines the resulting messages, while JT-CG prices states under a common current dual vector; the coordinator selects global states and checks certification. A cached conditional value is indexed by the routed observations, remaining depth, inherited feasibility restrictions, and all costs and restrictions of the remaining subtree. Position is part of this identity when it changes the subproblem. The computational study uses uniform observation weights and a common split penalty. Separator states remain distinct unless their master coefficients agree. Electronic Companion EC.3.4 gives the bound reuse conditions; the experiments distinguish fixed-task throughput from end-to-end solver runtime. 16
For parallel pricing, partition Ω𝑞 into disjoint blocks Ω𝑞ℎ , ℎ = 1, . . . , 𝐻𝑞 . Then 𝑟 𝑞 = min
min e 𝑐 𝑞 (𝜔).
(31)
1≤ℎ≤ 𝐻𝑞 𝜔 ∈Ω𝑞ℎ
Valid block bounds 𝑟 𝑞ℎ combine as
𝑟 𝑞 = min 𝑟 𝑞ℎ ≤ 𝑟 𝑞 .
(32)
1≤ℎ≤ 𝐻𝑞
All blocks, including unfinished ones, contribute valid bounds under the same dual vector to (32); completed blocks may return columns immediately.
5
Computational Experiments
The computational study has three parts. We first compare the proposed methods with existing exact OCT solvers. We then examine the effect of the exact reductions on formulation size and end-to-end solution runtime. Finally, we evaluate the computational impact of subtree contraction and parallel conditional-subtree evaluation.
5.1
Experimental Design
We use the 11 public classification datasets summarized in Table 2, which reports the number of observations, binary features, and classes after preprocessing. Numerical variables are converted to cumulative empiricaldecile predicates, with repeated thresholds removed, and categorical variables to equality indicators. All methods receive the same resulting binary matrices and use all observations for training. Maximum depths 𝐷 ∈ {2, 3, 4, 5} and split penalties 𝜆 ∈ {0, 0.01} give 88 benchmark settings. Table 2: Benchmark datasets. Dataset avila banknote compas diabetic fico give htru2 letter skin spambase transactions
Observations 𝑛
Binary features 𝐹
20,867 1,372 12,381 101,766 10,459 150,000 17,898 20,000 245,057 4,601 786,363
85 36 71 315 159 57 72 99 27 152 131
Classes |K |
12 2 2 3 2 2 2 26 2 2 2
Runs use an Intel Core i9-14900KF central processing unit (CPU), 64 GiB of host memory, and an NVIDIA RTX 4080 SUPER graphics processing unit (GPU). The nominal time limit is 600 seconds. Gurobi 13.0.3 is used to solve the LP models and the mixed-integer programming (MIP) models. JT runs use an absolute gap tolerance of 10−7 for numerical optimality certification. The lower bounds come from the methods’ full-domain certificates; upper bounds are attained by recovered trees. Each returned tree is independently rerouted and reevaluated under (2) to check its feasibility and objective. Our code and datasets are available in the GitHub repository (https://github.com/Tommytutu/JT-OCT). We compare JT-LP, JT-CG and JT-MP with the mixed-integer method BendersOCT (BOCT) (Aghaei et al., 2025) and the exact-search methods STreeD (van der Linden et al., 2023), MurTree (Demirović et al., 17
2022), GOSDT (Lin et al., 2020), Branches (Chaouki et al., 2025), and DL8.5 (Aglin et al., 2020). We additionally compare with RolloTree’s OCT-2 module (Organ et al., 2026) only at 𝐷 = 2 and 𝜆 = 0, under its complete-tree domain. We also report heuristic column generation (HCG) (Patel et al., 2024), using screened feature sets, and CART (Breiman et al., 1984) as a feasible-tree baseline. GOSDT results use gosdt-guesses (McTavish et al., 2022), version 1.0.4. For a binary tree, the leaf count is one plus the split count, so we subtract the constant 𝜆 from its leaf-penalized objective and bounds to match (2). Among the exact methods, The BendersOCT objective is modified to match the common training-loss and split-penalty objective. DL8.5 uses a maximum-depth constraint and permits smaller trees; its experiments here cover 𝜆 = 0. All external implementations are run on the same machine using their documented interfaces. The JT implementations allow early stopping and prohibit repeated features on a path. JT-LP solves the formulation after signature compression and endpoint elimination, using direct minimization when one cluster remains. At D2/D3, JT-CG uses a specialized exact shallow procedure. At D4/D5, it evaluates subtrees of private depth ℎ = 3 and uses bounds from unfinished searches as specified in Algorithm EC.1. Of the 44 settings, 42 enter the restricted-master loop. For transactions at both depths with 𝜆 = 0.01, the depth bound in (49) closes the gap before this loop. JT-MP uses complete min-sum elimination. The automatic conditional-evaluation policy selects CPU or GPU execution; for D4/D5 JT-CG, it selects CPU for the four banknote settings and GPU for the remaining 40. These D4/D5 runs use up to eight CPU workers; the shallow procedures retain their recorded thread settings.
5.2
Comparison with Existing Exact Methods
The comparison uses the common objective (2) and the method-specific domains described above. We report the shallow and deeper results separately to distinguish the specialized D2/D3 procedure from the D4/D5 restricted-master implementation. Table 3 reports returned objective values, runtimes, and optimality certificates. At depth two, the JT formulation specializes to the depth-two configuration structure of Organ et al. (2026) under matched modeling assumptions. RolloTree therefore provides a direct reference for the shallow formulation. For 𝜆 = 0, both RolloTree and JT-LP certify all 11 datasets, while their arithmetic-mean runtimes are 40.40 and 0.09 seconds, respectively. The JT-LP implementation reduces the explicit formulation before optimization and uses parallel computation in local-cost construction. BOCT certifies 2 of the 88 settings and reaches the time limit on most runs. Its numbers of variables and constraints increase with sample size, making the large datasets in this benchmark particularly demanding. For fixed depth, features, and classes, the size bounds of the JT formulation do not depend on the number of observations. This structural difference helps explain the runtime advantage of the JT methods. Among the external exact methods, STreeD certifies the largest number of settings, 77 of 88. JT-LP certifies 84, while JT-CG and JT-MP each certify 85. On the 77 settings jointly certified by JT-CG and STreeD, JT-CG is faster on 76, with a paired geometric-mean runtime ratio 𝑡STreeD /𝑡 JT-CG of 21.79. For D2/D3, all 44 settings are jointly certified, with JT-CG faster on all 44 and a geometric-mean ratio of 38.20. For D4/D5, the corresponding counts are 33 jointly certified settings and 32 faster cases, with a ratio of 10.31. Excluding the two cases certified before the restricted-master loop gives 9.38 on 31 jointly certified settings. The runtime difference decreases with depth. Using the unrounded arithmetic-mean runtimes underlying Table 3, the STreeD/JT-CG ratio is 28.42–31.35 at depth two, 10.27–12.03 at depth three, 6.50–8.72 at depth four, and 2.37–3.22 at depth five, where each range corresponds to the two values of 𝜆. Thus, the largest runtime differences occur at depths two and three. At depth five, the difference is more apparent in certification coverage: JT-CG certifies 19 of the 22 settings, compared with 12 for STreeD. Among the JT implementations, JT-CG has the lowest arithmetic-mean runtime in every depth–penalty group in Table 3. At D4/D5, the ratios of JT-MP to JT-CG mean runtimes range from 1.05 to 1.14, with identical certification counts. This difference is smaller than the corresponding comparison with STreeD. 18
Table 3: Optimization results by depth and split penalty. ObjVal and AverageRuntime are arithmetic means; OPT is the number of method-supplied certificates among 11 datasets. ObjVal Model
𝐷=2
𝐷=3
Panel A: 𝜆 = 0 CART 0.2597 0.2345 RolloTree 0.2466 — BOCT 0.2552 0.2322 HCG 0.2566 0.2332 DL8.5 0.2466 0.2188 GOSDT 0.2466 0.21849/11 MurTree 0.2466 0.2188 STreeD 0.2466 0.2188 Branches 0.2466 0.2192 JT-LP 0.2466 0.2188 JT-CG 0.2466 0.2188 JT-MP 0.2466 0.2188 Panel B: 𝜆 = 0.01 CART 0.2897 BOCT 0.2833 GOSDT 0.2674 MurTree 0.2674 STreeD 0.2674 Branches 0.2674 JT-LP 0.2674 JT-CG 0.2674 JT-MP 0.2674
AverageRuntime (s) 𝐷=4
OPT
𝐷=5 𝐷=2 𝐷=3 𝐷=4 𝐷=5 𝐷=2 𝐷=3 𝐷=4 𝐷=5
0.2135 0.1928 — — — — — — 40.40 — — — 0.2130 0.1928 558.30 600.93 601.52 602.07 0.2114 0.1927 79.29 111.86 185.27 282.58 0.2055 0.2262 2.03 126.82 412.71 503.39 0.08655/11 0.00572/11 3.33 45.61 132.89 73.38 0.18949/11 0.07024/11 2.20 12.49 160.95 437.76 0.1947 0.1788 2.20 4.80 133.83 381.09 0.2194 0.2352 8.55 42.78 80.14 79.10 0.1947 0.1712 0.09 1.52 27.63 201.90 0.1947 0.1706 0.07 0.40 20.59 160.96 0.1947 0.1705 0.23 0.55 23.52 174.92
— 11 1 — 11 11 11 11 11 11 11 11
— — 0 — 9 9 11 11 8 11 11 11
— — 0 — 4 4 9 10 2 11 11 11
— — 0 — 2 2 4 5 1 9 9 9
0.3027 0.3517 0.4555 — — — — 0.2863 0.3113 0.3700 548.67 601.19 601.29 601.48 0.2548 0.23669/11 0.05795/11 2.19 79.36 220.71 72.56 0.2548 0.227910/11 0.09746/11 3.51 4.21 107.82 355.55 0.2548 0.2476 0.2478 1.95 3.13 87.20 283.38 0.2548 0.2548 0.2548 10.58 67.27 137.89 146.69 0.2548 0.2476 0.2436 0.09 1.46 27.23 201.05 0.2548 0.2476 0.2436 0.07 0.30 10.00 88.09 0.2548 0.2476 0.2436 0.23 0.48 10.98 92.69
— 1 11 11 11 11 11 11 11
— 0 10 11 11 9 11 11 11
— 0 6 10 11 4 11 11 11
— 0 5 6 7 3 9 10 10
ObjVal averages returned feasible objectives, including CART fallback trees for BOCT runs without a solver incumbent; a subscript 𝑛/11 gives the number of available objectives. AverageRuntime averages recorded runtimes over attempted runs, including resource-limited runs. OPT counts each method’s certificates for its stated domain. RolloTree uses a complete-tree domain at 𝐷 = 2; DL8.5 uses a maximum-depth domain. Both are reported only at 𝜆 = 0. HCG uses screened features and has no full-domain certificate. The JT results compare implementations under their recorded CPU/GPU policies.
JT-LP is faster than JT-MP at depth two, whereas JT-MP has the lower mean runtime from depth three onward. The effect of the split penalty also differs across the three JT implementations. The runtime of JT-LP changes little between 𝜆 = 0 and 𝜆 = 0.01: changing the penalty changes the configuration costs but not the size of the reduced LP. The effect is larger for JT-CG and JT-MP. At depth five, the mean runtime decreases from 160.96 to 88.09 seconds for JT-CG and from 174.92 to 92.69 seconds for JT-MP when 𝜆 increases from 0 to 0.01. A positive split penalty enters the conditional lower bounds and can enable pruning before full subtree evaluation. STreeD shows the same direction of change in mean runtime at depths three through five. Figure 2 provides the corresponding distributional comparison. Panel (a) reports the cumulative number of settings certified as a function of runtime. Panel (b) reports the distribution of 𝑡STreeD /𝑡 JT over settings certified by both methods. The first panel therefore shows both the rate at which certificates are obtained and the final certification coverage, while the second shows how the runtime differences are distributed across individual benchmark settings. The three settings not certified by JT-CG within the time limit are all at depth five: diabetic for both values of 𝜆 and transactions for 𝜆 = 0. Their final lower and upper bounds, together with the complete per-instance objectives, gaps, runtimes, and termination statuses, are reported in Electronic Companion EC.4.
19
Number of jointly certified settings
Cumulative certified settings
STreeD (77/88) JT-LP (84/88) JT-CG (85/88) JT-MP (85/88)
80 60 40 20 0 0.01
0.1
1
10
100
40 JT-LP (𝑛 = 76) JT-CG (𝑛 = 77) JT-MP (𝑛 = 77)
30 20
12
11
10 4
0
6
17 12
23
18 13
9 5
1
<1
600
8
26
24
2021
=1
(a) Runtime (s)
(1, 5)
[5, 10)
[10, 20) [20, 50)
(b) Runtime ratio interval
≥ 50
Figure 2: Certification runtime profiles and paired runtime ratios relative to STreeD.
5.3
Effect of Structural Reduction
This experiment asks how much signature compression (SC) and endpoint elimination (EE) reduce the explicit formulation, and whether the smaller coordination system reduces coordination and end-to-end runtime. We use the depth-three complete-tree model with 𝜆 = 0, seven splits, eight nonempty leaves, no repeated feature on a path, and locally optimized terminal labels. LP-base is unreduced; LP+SC retains one minimum-cost representative per separator signature; LP+SC+EE also eliminates the endpoint clusters; and message passing (MP) eliminates the remaining chain. The three reduced variants share data, conditional costs, execution policy, and timing boundary. JT-LP in Section 5.2 is LP+SC+EE. Table 4: Effect of structural reduction in the depth-three complete-tree experiment with 𝜆 = 0. Data Dataset avila banknote compas diabetic fico give htru2 letter skin spambase transactions
𝑛 20,867 1,372 12,381 101,766 10,459 150,000 17,898 20,000 245,057 4,601 786,363
Number of columns 𝐹
LP-base
Number of rows
LP+SC LP+SC+EE LP-base
85 2,101,044 27,898 36 107,436 4,594 71 1,138,266 19,172 315 71,564,408 335,582 159 14,230,964 97,968 57 592,276 12,350 72 1,023,958 19,098 99 3,389,466 38,094 27 45,882 2,592 152 12,833,790 90,832 131 7,870,986 66,674
Runtime (s)
LP+SC LP+SC+EE LP-base LP+SC LP+SC+EE
13,618 14,369 14,369 2,074 2,560 2,560 9,232 10,015 10,015 143,013 192,888 192,888 47,882 50,249 50,249 5,966 6,445 6,445 8,874 10,300 10,300 18,690 19,507 19,507 1,188 1,435 1,435 44,928 46,060 46,060 32,614 34,195 34,195
87 36.069 38 0.186 73 13.109 317 M 161 T 59 5.819 74 10.773 101 61.871 29 0.266 154 333.997 133 T
0.484 0.012 0.061 6.497 0.640 0.184 0.065 0.798 0.055 0.587 5.133
0.444 0.008 0.043 6.038 0.550 0.178 0.050 0.746 0.054 0.483 5.217
MP 0.424 0.004 0.032 5.962 0.512 0.158 0.044 0.714 0.051 0.439 5.212
Notes. All reduced-model runs pass the independent tree and objective audit. M denotes a memory limit and T a time limit. LP+SC, LP+SC+EE, and MP use the same matched evaluation policy. LP-base is retained as an unreduced size and tractability reference.
SC reduces the total number of columns from 114,898,476 to 714,854, a factor of 160.7. EE reduces it further to 328,079 columns and reduces submitted equalities from 388,023 to 1,226. The reductions are especially pronounced for diabetic: 71.6 million columns in LP-base, 335,582 after SC, and 143,013 after SC+EE. LP-base reaches a memory limit on diabetic and time limits on fico and transactions; all reduced variants complete the 11 datasets. Phase runtimes separate coordination from cost construction. Across the 11 datasets, EE reduces coordination runtime by a geometric-mean factor of 2.57, whereas cost-preparation runtime changes by a 20
factor of 1.02 and total runtime by 1.16. A fixed-cost control, which supplies complete representative-cost tables to each coordinator, gives the same conclusion: on the 19 available D5 tables, EE reduces coordination runtime by factors of 2.42 for LP and 4.85 for eager CG. Thus SC produces most of the reduction in the explicit domain, while EE acts primarily on coordination; after cost evaluation becomes dominant, the latter has a smaller effect on total runtime.
5.4
Effect of Subtree Contraction
This experiment asks how contraction and private depth change the amount of conditional work. We compare MP with and without contraction on the 44 D4/D5 settings under CPU8 and a 600-second limit. The contracted variant uses private depth ℎ = 3; both variants use the same data and tree domain. Contraction raises certification from 26 to 29 settings. On the 26 joint certificates, it is faster in every pair, reduces arithmetic mean runtime from 133.56 to 23.64 seconds, and gives a geometric-mean speedup of 4.30. 150
50
Certified
44 40
Timeout
15
18
30
Mean runtime (s)
Number of settings
60
20 26
29
Without contraction
With contraction
10 0
133.56
Faster pairs: 26/26 GM speedup: 4.30×
120 90 60
23.64
30 0 Without contraction
(a) Certification coverage
With contraction
(b) Paired mean runtime
Figure 3: Subtree contraction under CPU8 and a 600-second limit. Panel (a) reports certification coverage over 44 D4/D5 settings; panel (b) reports arithmetic mean runtime on the 26 jointly certified settings. We compare private-subtree depths ℎ = 2 and ℎ = 3 using the same implementation under CPU8. Table 5 reports certification over all 44 settings and work statistics on the 20 certified at both depths. Increasing ℎ from two to three moves work from the explicit chain into larger private problems, reducing retained states and oracle calls enough to lower total runtime. Oracle calls at the two depths solve different private subproblems and therefore measure invocation counts, rather than equal-sized units of work. Table 5: Effect of private-subtree depth on 44 D4/D5 settings under CPU8. State and call counts are totals; runtimes are arithmetic means over the 20 jointly certified settings. At ℎ = 2, 16 runs reach the 200,000-state capacity and eight reach the time limit; at ℎ = 3, 14 reach the time limit. Private Certified Retained Private-subtree Mean Faster GM speedup depth settings states oracle calls runtime (s) pairs relative to ℎ = 2 ℎ=2 ℎ=3
5.5
20/44 30/44
983,728 9,304
295,636 4,337
31.78 2/20 21.22 18/20
1.00 3.28
Parallel Conditional Evaluation
We first measure throughput on identical conditional-subtree task lists. CPU1, CPU8, and GPU complete all three repetitions on 38, 41, and 44 of the 44 D4/D5 settings, respectively. On the 38 settings completed by all 21
three modes, the geometric-mean speedups over CPU1 are 4.41 for CPU8 and 9.81 for GPU. This fixed-task experiment isolates conditional evaluation from the state-selection decisions of the complete solvers. (a) Fixed-task completion
(b) Fixed-task speedup
41/44 40
30
20
10
0
9.81×
10
38/44 GM speedup over CPU1
Settings with three completed calls
44/44
8
6
4.41× 4
2
CPU1
CPU8
0
GPU
CPU8 38 settings
GPU 38 settings
Figure 4: Parallel evaluation of identical conditional-subtree tasks. Panel (a) reports settings for which all three repetitions finish within 600 seconds. Panel (b) reports geometric-mean speedups over CPU1 on the 38 settings completed by all three modes, using median runtime. We next compare CG and MP in matched complete solvers, sharing the evaluator, cache rules, initial feasible tree, hardware policy, and 600-second limit. Each method certifies 31 of 44 settings under CPU8 and 41 under Auto. Table 6 compares conditional work on the jointly certified settings that enter both coordination procedures. CG makes 4.8% fewer exact oracle calls under CPU8 and 7.8% fewer under Auto. Evaluation dominates runtime for both methods. The saved evaluations are partly offset by CG’s master solves: on these paired settings, the geometric-mean ratios 𝑡MP /𝑡 CG are 0.921 and 0.957. Table 6: Matched conditional work and runtime. Statistics use 29 jointly certified CPU8 settings and 39 jointly certified Auto settings that enter both coordination procedures. Calls are totals; runtimes are arithmetic means in seconds. Policy
Method
CPU8
CG MP CG MP
Auto
Exact oracle calls
Evaluation
RMP
Messages
Total
60,053 63,101 210,106 227,914
42.86 43.18 29.53 32.72
1.435 0.000 1.029 0.000
0.039 0.026 0.025 0.030
46.08 44.74 32.25 34.49
Finally, we compare CPU8 and Auto in the complete solvers. On the 31 settings certified under both policies, Auto gives geometric-mean speedups over CPU8 of 3.71 for CG and 3.80 for MP. Auto includes the tested CPU/GPU selection and batching policy; the fixed-task experiment above provides the direct throughput comparison on an identical workload.
6
Conclusion
This paper develops an exact linear programming approach to optimal classification trees of any prescribed maximum depth with binary features. The model accommodates early stopping and minimum leaf support, and an optimal tree can be recovered from an optimal LP solution. It describes tree decisions without introducing variables and constraints for individual training observations; the data determine the costs and 22
feasibility of these decisions. Exact reductions preserve the optimal objective while shrinking the model and separating conditional-subtree optimization from the task of combining compatible decisions. This structure supports two exact solution methods, JT-CG and JT-MP, and parallel evaluation of the conditional-subtree problems. The experiments show that the reductions substantially decrease the explicit model size and that parallel subtree evaluation accelerates the resulting solution methods. Across 88 settings from 11 datasets, four depths, and two split penalties, JT-CG and JT-MP each certify 85 settings, compared with 77 for STreeD. On the 77 settings certified by both JT-CG and STreeD, JT-CG achieves a geometric-mean speedup of 21.79. The matched comparisons show that JT-CG solves fewer conditional-subtree problems, while JT-MP combines their results faster, leading to similar overall runtimes. The remaining depth-five settings highlight the difficulty of proving optimality after a good tree has been found. Stronger bounds on conditional subtree costs and more selective allocation of search effort are therefore promising directions for solving deeper OCT problems. The formulation also provides a basis for studying other additive prediction losses and multiway classification trees.
Data and Code Availability The Electronic Companion contains proofs, certificate details, and supporting computational results. The anonymized reproducibility artifact supplied with the submission contains preprocessing scripts, exact commands, software versions, raw logs, and per-instance outputs.
References Sina Aghaei, Andrés Gómez, and Phebe Vayanos. Strong optimal classification trees. Operations Research, 73(4):2223–2241, 2025. Gaël Aglin, Siegfried Nijssen, and Pierre Schaus. Learning optimal decision trees using caching branchand-bound search. Proceedings of the AAAI Conference on Artificial Intelligence, 34(4):3146–3153, 2020. Zacharie Alès, Valentine Huré, and Amélie Lambert. New optimization models for optimal classification trees. Computers & Operations Research, 164:106515, 2024. Brandon C. Alston, Hamidreza Validi, and Illya V. Hicks. Mixed integer linear optimization formulations for learning optimal binary classification trees. INFORMS Journal on Computing, 2026. Published online March 12. Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Machine Learning, 106:1039–1082, 2017. Leo Breiman, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone. Classification and Regression Trees. Wadsworth, Belmont, CA, 1984. Catalin E. Brita, Jacobus G. M. van der Linden, and Emir Demirović. Optimal classification trees for continuous feature data using dynamic programming with branch-and-bound. Proceedings of the AAAI Conference on Artificial Intelligence, 39(11):11131–11139, 2025. Emilio Carrizosa, Cristina Molero-Río, and Dolores Romero Morales. Mathematical optimization in classification and regression trees. TOP, 29:5–33, 2021.
23
Ayman Chaouki, Jesse Read, and Albert Bifet. Branches: Efficiently seeking optimal sparse decision trees via AO*. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 7430–7484, 2025. George B. Dantzig and Philip Wolfe. Decomposition principle for linear programs. Operations Research, 8 (1):101–111, 1960. Emir Demirović, Anna Lukina, Emmanuel Hébrard, Jeffrey Chan, James Bailey, Christopher Leckie, Kotagiri Ramamohanarao, and Peter J. Stuckey. MurTree: Optimal decision trees via dynamic programming and search. Journal of Machine Learning Research, 23(26):1–47, 2022. Murat Firat, Guillaume Crognier, Adriana F. Gabor, Cor A. J. Hurkens, and Yingqian Zhang. Column generation based heuristic for learning classification trees. Computers & Operations Research, 116:104866, 2020. Oktay Günlük, Jayant Kalagnanam, Minhan Li, Matt Menickelly, and Katya Scheinberg. Optimal decision trees for categorical data via integer programming. Journal of Global Optimization, 81(1):233–260, 2021. Hao Hu, Mohamed Siala, Emmanuel Hébrard, and Marie-José Huguet. Learning optimal decision trees with MaxSAT and its integration in AdaBoost. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, pages 1170–1176, 2020. Xiyang Hu, Cynthia Rudin, and Margo Seltzer. Optimal sparse decision trees. In Advances in Neural Information Processing Systems, volume 32, 2019. Laurent Hyafil and Ronald L. Rivest. Constructing optimal binary decision trees is NP-complete. Information Processing Letters, 5(1):15–17, 1976. Petr Kolman and Martin Koutecký. Extended formulation for CSP that is compact for instances of bounded treewidth. The Electronic Journal of Combinatorics, 22(4):P4.30, 2015. Frank R. Kschischang, Brendan J. Frey, and Hans-Andrea Loeliger. Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 47(2):498–519, 2001. Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, and Margo Seltzer. Generalized and scalable optimal sparse decision trees. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6150–6160, 2020. R. Kipp Martin, Ronald L. Rardin, and Brian A. Campbell. Polyhedral characterization of discrete dynamic programming. Operations Research, 38(1):127–138, 1990. Rahul Mazumder, Xiang Meng, and Haoyue Wang. Quant-BnB: A scalable branch-and-bound method for optimal decision trees with continuous features. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 15255–15277. PMLR, 2022. Hayden McTavish, Chudi Zhong, Reto Achermann, Ilias Karimalis, Jacques Chen, Cynthia Rudin, and Margo Seltzer. Fast sparse decision tree optimization via reference ensembles. Proceedings of the AAAI Conference on Artificial Intelligence, 36(9):9604–9613, 2022. Carla Michini and Zachary Zhou. A polyhedral study of multivariate decision trees. INFORMS Journal on Optimization, 7(1):61–82, 2024. 24
İbrahim Muter, Ş. İlker Birbil, and Kerem Bülbül. Simultaneous column-and-row generation for large-scale linear programs with column-dependent-rows. Mathematical Programming, 142(1–2):47–82, 2013. Nina Narodytska, Alexey Ignatiev, Filipe Pereira, and Joao Marques-Silva. Learning optimal decision trees with SAT. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, pages 1362–1368, 2018. Zeynel Batuhan Organ, Enis Kayış, and Taghi Khaniyev. Rolling lookahead learning for optimal classification trees. IISE Transactions, 58(10):1206–1221, 2026. Krunal Kishor Patel, Guy Desaulniers, and Andrea Lodi. An improved column-generation-based matheuristic for learning classification trees. Computers & Operations Research, 165:106579, 2024. Remy Spliet. A simple perspective on simultaneous column and row generation. Operations Research Forum, 5(3):69, 2024. Shivaram Subramanian and Wei Sun. Scalable optimal multiway-split decision trees with constraints. Proceedings of the AAAI Conference on Artificial Intelligence, 37(8):9891–9899, 2023. Jacobus van der Linden, Mathijs de Weerdt, and Emir Demirović. Necessary and sufficient conditions for optimal decision trees using dynamic programming. In Advances in Neural Information Processing Systems, volume 36, pages 9173–9212, 2023. Hélène Verhaeghe, Siegfried Nijssen, Gilles Pesant, Claude-Guy Quimper, and Pierre Schaus. Learning optimal decision trees using constraint programming. Constraints, 25(3–4):226–250, 2020. Sicco Verwer and Yingqian Zhang. Learning optimal classification trees using a binary linear program formulation. Proceedings of the AAAI Conference on Artificial Intelligence, 33(1):1625–1632, 2019. Martin J. Wainwright and Michael I. Jordan. Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning, 1(1–2):1–305, 2008.
25
Electronic Companion EC.1
Proofs for the Junction-Tree Formulation
EC.1.1
Validity of the cluster chain
Proof. Proof of Proposition 1. Fix an internal position 𝑣. A cluster 𝐶𝑞 contains 𝑣 exactly when 𝑣 lies on the path from the root to 𝑞, including both endpoints. These indices occur consecutively in lexicographic order, so the clusters containing 𝑣 form a connected part of J . A terminal position belongs to only one cluster. The running-intersection condition in Definition 1 therefore holds. □
EC.1.2
Convex-hull property and tree recovery
Proof. Proof of Proposition 2. Fix 𝑇 ∈ T . For every split node 𝑣 ∈ 𝐵(𝑇), the term 𝜆 𝑣, 𝑓𝑣 /𝑚 𝑣 occurs in each of the 𝑚 𝑣 clusters containing 𝑣. If 𝑣 ∈ 𝐿 (𝑇) is a prediction leaf, then ℓ𝑣 (𝑇 | 𝐶𝑞 ) is the same for every cluster containing 𝑣, because each such cluster contains the complete ancestor path of 𝑣. Consequently, ∑︁ 𝑞∈ Q
∑︁ 𝜆 𝑣, 𝑓 ∑︁ ∑︁ ℓ𝑣 (𝑇 | 𝐶𝑞 ) 𝑣 + 𝑚𝑣 𝑚𝑣 𝑣 ∈ 𝐵(𝑇 ) 𝑞:𝑣 ∈𝐶𝑞 𝑣 ∈ 𝐿 (𝑇 ) 𝑞:𝑣 ∈𝐶𝑞 ∑︁ 1 ∑︁ 1{𝑇 (𝑧 𝑖 ) ≠ 𝑦 𝑖 } = 𝐽 (𝑇). = 𝜆 𝑣, 𝑓𝑣 + 𝑛 𝑖∈𝐼
𝑐 𝑞 (𝑇 | 𝐶𝑞 ) =
∑︁
𝑣 ∈ 𝐵(𝑇 )
□ Proof. Proof of Theorem 1. OCT configuration–tree correspondence. Restrict a feasible tree 𝑇 ∈ T to each cluster. Every structural, path, and individual-leaf condition has its full scope in a cluster, so these restrictions are admissible and agree on separators. Conversely, choose separator-consistent admissible configurations. Running intersection makes the action at each position unique. Every parent–child pair is covered, so the assembled actions enforce an active root, active children exactly when the parent splits, inactive descendants after a prediction, and no terminal split. Each prediction position occurs with its complete ancestor path; its routed observations and local feasibility checks therefore coincide with those of the assembled tree. Restriction and assembly are inverse maps, giving the claimed bijection and conv{𝑥 𝑇 : 𝑇 ∈ T } ⊆ 𝑃. (33) Junction-tree convex decomposition. The standard junction-tree decomposition (Wainwright and Jordan, 2008, Proposition 2.1) and configuration-LP integrality argument (Kolman and Koutecký, 2015, Lemma 2.1 and Theorem 1.1) give a constructive recovery procedure. Root the junction tree and select a positive-weight configuration of 𝑥 ∈ 𝑃 there. Each separator equation supplies a positive-weight child configuration agreeing with the selected parent. Continuing gives a consistent selection and hence a feasible tree 𝑇, all of whose selected coordinates have positive weight. Let 𝛿 be the smallest weight in 𝑥 among the configurations selected for 𝑇. Then 0 < 𝛿 ≤ 1. If 𝛿 = 1, normalization gives 𝑥 = 𝑥 𝑇 . Otherwise, (𝑥 − 𝛿𝑥 𝑇 )/(1 − 𝛿) ∈ 𝑃. The numerator is nonnegative, has cluster sums 1 − 𝛿, and satisfies the separator equations. Each step removes a positive coordinate without introducing any, so iteration terminates and yields ∑︁ ∑︁ 𝑥= 𝑝𝑇 𝑥𝑇 , 𝑝 𝑇 ≥ 0, 𝑝 𝑇 = 1. (34) 𝑇∈T
𝑇∈T
26
Together with (33), this yields (10). Í Objective value and tree recovery. Proposition 2 makes the objective at 𝑥 equal to 𝑇 𝑝 𝑇 𝐽 (𝑇). Hence the LP and the IP have value OPT𝐷 . If 𝑥 is optimal, every tree with 𝑝 𝑇 > 0 in this decomposition is optimal; otherwise their average cost would exceed OPT𝐷 . The support selection above therefore recovers an optimal tree. □ Proof. Proof of Corollary 1. Setting 𝑥 𝑞 𝜔 = 0 for excluded configurations defines a face of 𝑃. After zero extension, the restricted master is exactly this face: only separator equations that reduce to 0 = 0 are omitted. In (34), a zero coordinate excludes every tree using that configuration, whereas every tree using only retained b 𝑞 for all 𝑞 ∈ Q}. It is configurations belongs to the face. Thus the face equals conv{𝑥 𝑇 : 𝑇 ∈ T , 𝑇 | 𝐶𝑞 ∈ Ω empty if no compatible tree remains; otherwise all of its extreme points are integral, and every linear objective attains an optimum at one of them. □
EC.1.3
Depths two and three
In the following shallow formulations, infeasible rule tuples are omitted, equivalently by fixing their variables to zero. For complete split-only trees with locally optimized terminal labels, a depth-two configuration consists of root rule 𝑓 and child rule 𝑔 on branch 𝑏 ∈ {0, 1}. With 𝑐 𝑏𝑓 𝑔 denoting its minimized local cost, the formulation is ∑︁ ∑︁ min 𝑐 𝑏𝑓 𝑔 𝑥 𝑏𝑓 𝑔 𝑥 ≥0
s.t.
𝑏∈ {0,1} 𝑓 ,𝑔∈ F
∑︁
𝑥 𝑏𝑓 𝑔 = 1
𝑓 ,𝑔∈ F
∑︁
𝑥 0𝑓 𝑔 =
𝑔∈ F
𝑏 ∈ {0, 1}, 𝑥 1𝑓 𝑔
∑︁
(35)
𝑓 ∈ F.
𝑔∈ F
This is the depth-two structure studied by Organ et al. (2026). At depth three, let 𝑥 𝑎𝑏 𝑓 𝑔ℎ select rules 𝑓 , 𝑔, and ℎ at positions 𝜖, 𝑎, and 𝑎𝑏. In addition to one normalization equation for each 𝑎𝑏 ∈ {00, 01, 10, 11}, the separator equations are ∑︁ ∑︁ 𝑥 00 𝑥 01 𝑓,𝑔 ∈ F, 𝑓 𝑔ℎ = 𝑓 𝑔ℎ ℎ ∑︁
𝑥 01 𝑓 𝑔ℎ =
ℎ ∑︁
𝑔,ℎ
∑︁
𝑥 10 𝑓 𝑔ℎ
𝑓 ∈ F,
𝑥 11 𝑓 𝑔ℎ
𝑓,𝑔 ∈ F.
𝑔,ℎ
𝑥 10 𝑓 𝑔ℎ =
∑︁
ℎ
ℎ
(36)
The outer equations match joint root–child actions; the middle equation matches the root. Under matched rules, feasibility filters, and losses, these are the four configuration groups in Appendix A of the 2023 preprint of Organ et al. (2026), in the order (00, 01, 10, 11). Theorem 1 allows arbitrary depth, early stopping, and ancestor-local feasibility. For reference, the split-only coefficients at depths two and three are 1 𝑐 𝑏𝑓 𝑔 = 𝜆 𝜖 , 𝑓 + 𝜆 𝑏,𝑔 + 2
and
1 ∑︁
2
(37)
1 1{𝑦 𝑖 ≠ 𝑘 }. 𝑘∈K 𝑛 𝑑=0 𝑖 ∈ 𝐼: 𝑧 =𝑎, 𝑧 =𝑏, 𝑧 =𝑑
(38)
𝑑=0
1 1 𝑐 𝑎𝑏 𝑓 𝑔ℎ = 𝜆 𝜖 , 𝑓 + 𝜆 𝑎,𝑔 + 𝜆 𝑎𝑏,ℎ + 4
1 1{𝑦 𝑖 ≠ 𝑘 }. 𝑛 𝑖 ∈ 𝐼: 𝑧 =𝑏, 𝑧 =𝑑
min 𝑘∈K
1 ∑︁
∑︁
𝑖𝑔
𝑖𝑓
∑︁
min
𝑖𝑓
27
𝑖𝑔
𝑖ℎ
They follow directly from the multiplicities in (6); terminal labels can be minimized locally because the matched split-only models do not couple terminal predictions.
EC.2
Proofs for Exact Reductions
For private depth ℎ, put 𝑎 = 𝐷 − ℎ and let 𝐴𝑡 be the strict ancestors of 𝑡 ∈ Q ℎ . Write Uℎ (𝑡, 𝜎) for feasible private completions under separator assignment 𝜎, and 𝐽𝑡 (𝑈; 𝜎) for their prediction loss and split penalties. The allocated ancestor cost is 𝑔𝑡 (𝜎) in (41). Proof. Proof of Proposition 3. Let 𝑇 denote the aggregation map in (15). If 𝑥 ∈ 𝑃, summing the JT-LP normalization row over the partition {𝜔 ∈ Ω𝑞 : 𝛾𝑞 (𝜔) = 𝜂} 𝜂 ∈Γ𝑞 gives (14b). For an edge 𝑒 = {𝑞, 𝑟 } and assignment 𝜎 ∈ Σ𝑒 , ∑︁ ∑︁ (𝑇𝑥)𝑞 𝜂 = 𝑥𝑞 𝜔 . 𝜂 ∈Γ𝑞 :𝜂𝑒 =𝜎
𝜔 ∈Ω𝑞 :𝜔 | 𝑆𝑒 =𝜎
The analogous identity holds at 𝑟, so (8c) gives (14c). Hence 𝑇 (𝑃) is contained in the compressed region. Conversely, let 𝑦 satisfy (14) and define ( 𝑦 𝑞 𝜂 , 𝜔 = 𝜔★𝑞 (𝜂) for some 𝜂 ∈ Γ𝑞 , 𝑥𝑞 𝜔 = 0, otherwise. The stored representative has signature 𝜂, so the normalization and separator marginals of 𝑥 equal those of 𝑦. Thus 𝑥 ∈ 𝑃 and 𝑇𝑥 = 𝑦, which proves equality of the feasible-region image. By Theorem 1, 𝑃 is the convex hull of tree-selection vectors. Their images under 𝑇 select one signature per cluster and are integral. The compressed region is therefore also integral. For arbitrary 𝑥 ∈ 𝑃, the definition of 𝑐¯𝑞 gives ∑︁ ∑︁ 𝑐¯𝑞 (𝜂) (𝑇𝑥)𝑞 𝜂 ≤ 𝑐 𝑞 (𝜔)𝑥 𝑞 𝜔 . 𝑞, 𝜂
𝑞, 𝜔
For the lift above, equality holds because 𝑐 𝑞 (𝜔★𝑞 (𝜂)) = 𝑐¯𝑞 (𝜂). Applying the two maps to optimal solutions proves equality of the optimal values. If 𝑦 is integral, exactly one signature is selected at each cluster and the displayed lift selects exactly one representative there, so the lift is integral and has the same objective value. □ Proof. Proof of Proposition 4. Fix 𝑡 ∈ Q ℎ and a feasible external separator assignment 𝜎 for the block B𝑡 . Running intersection and the ancestor-local predicates give a bijection between the completions in Uℎ (𝑡, 𝜎) and the mutually consistent original configurations in B𝑡 that agree with 𝜎 on the external separators. This remains true when an ancestor predicts, in which case all private positions are inactive. Each strict ancestor 𝑣 occurs in all 2ℎ−1 clusters of the block, giving total coefficient 2ℎ−1 /2𝐷−1− |𝑣 | = 2− (𝑎− |𝑣 | ) . Each private position has all its occurrences in this block, so its coefficients sum to one. The block cost is therefore 𝑔𝑡 (𝜎) + 𝐽𝑡 (𝑈; 𝜎); minimizing gives (18), including the empty-domain convention. The external signature records all strict ancestors: for 𝑎 ≥ 1, a sibling group shares them; for 𝑎 = 0, the signature is empty. Compression thus minimizes exactly the private cost. For ℎ = 1, the block is one original cluster, giving the SC identity. Recompression is idempotent while its interface is unchanged. □ Proof. Proof of Proposition 6. Because 𝑞 is a leaf, its signature is its assignment 𝜎 on 𝑆 𝑒 . The separator equations therefore imply (20). Summing those identities over 𝜎 ∈ Σ𝑒 and using the normalization at 𝑟 shows that the normalization at 𝑞 is redundant. 28
Projection deletes only the coordinates and constraints of 𝑞. Conversely, (20) uniquely lifts a reduced feasible vector: feasibility filtering supplies an admissible state at 𝑞 for each separator assignment used at 𝑟. The lift satisfies the deleted separator and normalization rows, so the two maps are inverse. Finally, substitution gives ∑︁ ∑︁ 𝑐¯𝑟 (𝜂)𝑦 𝑟 𝜂 + 𝑐¯𝑞 (𝜎)𝑦 𝑞 𝜎 𝜂 ∈Γ𝑟
=
∑︁ 𝜂 ∈Γ𝑟
𝜎 ∈Γ𝑞
[ 𝑐¯𝑟 (𝜂) + 𝑐¯𝑞 (𝜂𝑒 )] 𝑦 𝑟 𝜂 =
∑︁ 𝜂 ∈Γ𝑟
e 𝑐𝑟 (𝜂)𝑦 𝑟 𝜂 .
Thus the bijection preserves objective values. It also preserves integral vectors. Combining the recovered signatures with the stored representatives from Proposition 3 recovers an optimal JT-LP solution and hence an optimal tree by Theorem 1. □ A later leaf may retain components from eliminated neighbors. Recompressing its current potential on its remaining separator gives ∑︁ 𝑀𝑞→𝑟 (𝜎) = min 𝑐¯𝑞 (𝜂) + 𝑀𝑘→𝑞 (𝜂 { 𝑘,𝑞 } ) . 𝜂 ∈Γ𝑞 :𝜂𝑒 =𝜎 𝑘 ∈ 𝑁J (𝑞)\{𝑟 }
(39)
Proposition 6 applies at each step, proving exactness by induction. Equation (39) is the compressed form of the recursion in Section 4.2. Derivation of the depth-three counts. Before compression, each of the four clusters has 𝐹 3 split configurations. Minimizing its private deepest split conditional on the two ancestor splits leaves 𝐹 2 signatures, so the first two counts are 4𝐹 3 and 4𝐹 2 . Eliminating 𝐶00 and 𝐶11 leaves the two 𝐹 2 variable arrays, giving 2𝐹 2 variables. There are 𝐹 root-consistency rows and one retained normalization row. To verify independence, take a linear combination with coefficient 𝜆 𝑎 on the consistency row for 𝑎 and coefficient 𝜇 on the normalization 𝑅 is −𝜆 , so all 𝜆 = 0. The coefficient of each 𝑦 𝐿 is then 𝜇, so 𝜇 = 0. Hence row. The coefficient of each 𝑦 𝑎𝑐 𝑎 𝑎 𝑎𝑏 the 𝐹 + 1 rows are linearly independent.
EC.2.1
Configuration Counts and Subtree Contraction
With all 𝐹 rules allowed repeatedly and no extra feasibility filters, a base configuration either splits at its 𝐷 internal positions and labels both terminals, or predicts after 𝑗 < 𝐷 splits and leaves the remaining positions inactive. Hence 𝐷−1 ∑︁ 𝐷 2 |Ω𝑞 | = 𝐹 𝐾 + 𝐾 𝐹 𝑗. (40) 𝑗=0
For a split-only model with terminal labels optimized locally, the first term becomes 𝐹 𝐷 and the second is absent, giving (11). If repeated rules on a path are forbidden, replace 𝐹 𝑗 by the falling factorial (𝐹) 𝑗 = 𝐹 (𝐹 − 1) · · · (𝐹 − 𝑗 + 1), with (𝐹)0 = 1 and (𝐹) 𝑗 = 0 for 𝑗 > 𝐹. Additional local restrictions can only reduce these counts. The same partition by the first prediction position proves (22); without repeated Í rules its unfiltered count is (𝐹) 𝑎 + 𝐾 𝑎−1 𝑗=0 (𝐹) 𝑗 . Candidate arrays may use the larger repeated-rule index set and exclude infeasible entries during pricing; array capacity therefore need not equal the number of feasible columns. Conditional costs follow the recurrence in Section 4.1. The next result shows that one minimizing private completion per ancestor assignment preserves the optimal value. 29
Proof. Proof of Proposition 5. The enlarged cluster is 𝐶𝑡(ℎ) = 𝐴𝑡 ∪ 𝐵𝑡(ℎ) , where 𝐵𝑡(ℎ) is the private subtree. Clusters containing an upper position are consecutive in lexicographic order; each private position belongs to one cluster. Running intersection therefore holds, and every private decision occurs with the ancestors needed to evaluate its loss and feasibility. For |𝑣| < 𝑎, the multiplicity is 𝑚 𝑣(ℎ) = 2𝑎− |𝑣 | ; private positions have multiplicity one. The allocated ancestor term is ∑︁ ℓ𝑣 (𝜎) 𝑔𝑡 (𝜎) = . (41) 2𝑎− |𝑣 | 𝑣∈ 𝐴 𝑡
The same counting argument as in Proposition 2 shows that the enlarged cluster costs sum to 𝐽 (𝑇) for any feasible tree. The configuration–tree correspondence in Electronic Companion EC.1 applies to these enlarged clusters as well. Classical junction-tree exactness (Wainwright and Jordan, 2008, Proposition 2.1) therefore makes their complete normalized separator model integral. At fixed 𝑡 and 𝜎, all private completions have identical master coefficients. Replacing them by a minimizer of (17) preserves feasibility and cannot increase cost. Applied to an optimal full tree, this gives a representative selection costing at most OPT𝐷 . Conversely, consistent representatives assemble into a feasible tree with the same cost, proving the reverse inequality. Retaining one minimizer per ancestor assignment is a column restriction of the enlarged integral model; Corollary 1 therefore proves integrality. The support traversal in Theorem 1, followed by insertion of the stored subtrees, recovers an optimal tree even from a fractional optimum. Cross-group constraints can be accommodated by enlarging the interface to retain the private decisions on which they depend. □
EC.3
Certificates and Conditional-Cost Bounds
Subtree searches can provide useful bounds before reaching optimality. This section explains how lower bounds and feasible subtree solutions guide further evaluation and provide certificates for the complete tree.
EC.3.1
Cost Intervals and Adaptive Message Passing
Extend Ξ𝑡 to include candidate assignments with unresolved feasibility; those without a feasible completion have exact cost +∞. For every state, including those absent from the RMP, maintain 𝜅 𝑡 (𝜎) = 𝑔𝑡 (𝜎) + 𝑉 ℎ (𝑡, 𝜎) ≤ 𝜅 𝑡 (𝜎) ≤ 𝜅 𝑡 (𝜎) = 𝑔𝑡 (𝜎) + 𝑉 ℎ (𝑡, 𝜎).
(42)
Retain a feasible subtree for each finite upper cost. Combine bounds by taking the maximum lower and minimum upper value; exact evaluation closes the interval. Section EC.3.4 gives the initial bounds. Adaptive message passing. Apply the recursion in Section 4.2 to all lower costs and to the feasible upper costs. Refine unresolved states in a minimizing lower-cost selection until the certified gap closes. The following result justifies this procedure. Proposition 9 (Interval certificate and finite refinement). Let A contain all separator-consistent candidatestate selections, with infeasible completions costing +∞. Assume T ≠ ∅, 𝜅 ≤ 𝜅 ≤ 𝜅 over the full domain, and a feasible realization for every finite upper cost. Put ∑︁ ∑︁ ∑︁ 𝐿 = min 𝜅 𝑡 (𝑠𝑡 ), 𝑈 = min 𝜅 𝑡 (𝑠𝑡 ), 𝑠 − ∈ arg min 𝜅 𝑡 (𝑠𝑡 ). (43) 𝑠∈ A
𝑡
𝑠∈ A
𝑡
30
𝑠∈ A
𝑡
Assume the lower costs are bounded below and an initial feasible tree is available. Then 𝐿 ≤ OPT𝐷 ≤ 𝑈, and, whenever the upper costs along 𝑠 − are finite, ∑︁ 0≤𝑈−𝐿 ≤ (44) 𝜅 𝑡 (𝑠𝑡− ) − 𝜅 𝑡 (𝑠𝑡− ) . 𝑡
An independently verified incumbent may further reduce 𝑈. In exact arithmetic, resolving at least one unresolved selected state whenever the gap is positive terminates with an optimal tree after at most 𝑁unresolved resolutions. Here 𝑁unresolved counts initially unresolved states, exact values are retained, and resolution includes proving infeasibility. This bound does not count partial oracle calls, message sweeps, or runtime. Recompute both message arrays after refinement; the proof is in Section EC.3.3.
EC.3.2
Column Generation with Cost Bounds
The RMP retains feasible representatives with their upper costs. Lower costs on the full candidate domain yield a pricing certificate. For the current RMP dual, extend absent separator multipliers by zero and set ∑︁ 𝑠𝑡𝑒 𝜋𝑒, 𝜎 | 𝑆𝑒 . 𝑟 𝑡 = min 𝜅 𝑡 (𝜎) − 𝛼𝑡 − 𝜎 ∈Ξ𝑡 𝑒∈𝐸 (𝑡 )
(45)
The minimum covers all states, evaluated or not; block bounds combine as in (32). With 𝛾𝑡 = min{0, 𝑟 𝑡 }, the inequality 𝜅 𝑡 ≤ 𝜅 𝑡 makes (𝛼 + 𝛾, 𝜋) exact-cost dual feasible. Thus ∑︁ ∑︁ 𝛼𝑡 + min{0, 𝑟 𝑡 } ≤ OPT𝐷 . (46) 𝑡 ∈ Qℎ
𝑡 ∈ Qℎ
Í The RMP uses feasible upper costs; its optimal dual objective is 𝑡 𝛼𝑡 . Equation (46) remains a lower bound when retained costs are unresolved. For configuration-cost bounds 𝑐 𝑞 (𝜔) ≤ 𝑐 𝑞 (𝜔), message passing gives a second certificate: ∑︁ ∑︁ LBJT = min 𝑐 𝑞 (𝜔)𝑥 𝑞 𝜔 ≤ OPT𝐷 . (47) 𝑥∈𝑃
𝑞 ∈ Q 𝜔 ∈Ω𝑞
For 𝜀-optimality, exact clusterwise pricing with tolerance 𝜏 requires 2𝐷−ℎ 𝜏 ≤ 𝜀. Both certificates cover the full domain, including states absent from the RMP. A state is promising when the expression in (45) gives a negative reduced-cost lower bound. Algorithm EC.1 permits refinement both inside and outside the RMP. Conditional-cost bounds are reusable for the same subproblem. Reduced-cost bounds use a fixed dual and must be recomputed when it changes. Updating a retained column changes the RMP objective, so its earlier optimum is no longer the current RMP value; the associated global lower certificate remains valid. The implementation retains columns and exact costs and re-solves each batch, except for the D5 fico and spambase runs, which use four batches.
EC.3.3
Proofs and Finite Termination
Proof. Proof of Proposition 7. Choose a feasible-tree cost 𝑧¯ and 𝐻 > 𝑧¯. In (23), replace an empty conditional b 𝑐 . Nonnegative minimum by 𝐻, leaving other recursion steps unchanged; denote these finite messages by 𝑀 local costs make every root assignment with an infeasible component cost at least 𝐻, whereas a feasible assignment costs 𝑧¯. The modified root minimum remains OPT𝐷 . 31
Algorithm EC.1 JT-CG with subtree cost bounds 1 2 3 4 5 6 7
Input: Candidate domains Ξ𝑡 , feasible tree 𝑇 0 , tolerance 𝜀, resource limit, and finite RMP interval 𝑏. Initialize valid intervals on Ξ𝑡 . Retain the feasible representatives of 𝑇 0 and all induced separator rows; set UB = 𝐽 (𝑇 0 ) and a valid LB. Solve the upper-cost RMP. Obtain its dual, extend absent row multipliers by zero, and recover a feasible tree to update UB. Bound pricing over the full domain under this dual. Update LB using (46), lower-cost messages, and the depth bound. Stop if UB − LB ≤ 𝜀. Evaluate promising absent states. Retain intervals from incomplete solves; add exact-cost improving columns and their induced rows. Remove proven infeasible states from further evaluation. Refine promising unresolved retained states. Update intervals, feasible representatives, column objective coefficients, and UB. After at most 𝑏 batches, or when a new dual is needed, return to step 2; otherwise repeat steps 3–5 using the same dual. Retain each certificate with the dual and bounds used to compute it. On a resource stop, return the incumbent tree and the last valid bounds.
Orient every edge from a child 𝑞 to its parent 𝑝. In the full-domain version of (25), the multiplier on this edge has sign +1 in the constraint for 𝑞 and sign −1 in the constraint for 𝑝. For every nonroot cluster 𝑞 and configuration 𝜔 ∈ Ω𝑞 , the message definition gives ∑︁ 𝑐 𝑐 b𝑞→ b𝑟→𝑞 𝑀 (𝜔| ) − 𝑀 (𝜔| 𝑆𝑟𝑞 ) ≤ 𝑐 𝑞 (𝜔). 𝑆 𝑝 𝑞𝑝 𝑟 child of 𝑞
𝑐 b𝑞→ This is the dual constraint at 𝑞 after setting 𝛼𝑞 = 0 and 𝜋𝑒 𝜎 = 𝑀 𝑝 (𝜎). At the root, (24) gives ∑︁ 𝑐 b𝑟→𝑞 OPT𝐷 − 𝑀 (𝜔| 𝑆𝑟𝑞0 ) ≤ 𝑐 𝑞0 (𝜔), 𝜔 ∈ Ω𝑞0 . 0 𝑟 child of 𝑞0
Í Hence the proposed multipliers are dual feasible. Their objective is 𝑞 𝛼𝑞 = OPT𝐷 . Message backtracking supplies a feasible tree of the same value by (24) and Theorem 1. Weak duality then makes the recovered tree and the displayed multipliers primal–dual optimal. □ Í Proof. Proof of Proposition 8. Strong duality gives 𝑧 𝑅 = 𝑞 𝛼𝑞 . Extend absent separator-row multipliers by zero, and set 𝛾𝑞 = min{0, 𝑟 𝑞 } and e 𝛼𝑞 = 𝛼𝑞 + 𝛾𝑞 . For every full-domain column (𝑞, 𝜔), ∑︁ 𝑐 𝑞 (𝜔) − e 𝛼𝑞 − 𝑠𝑞𝑒 𝜋𝑒, 𝜔 | 𝑆𝑒 = e 𝑐 𝑞 (𝜔) − 𝛾𝑞 𝑒∈𝐸 (𝑞)
≥ 𝑟 𝑞 − 𝛾𝑞
≥ 𝑟 𝑞 − min{0, 𝑟 𝑞 } ≥ 0. Í Thus (e 𝛼, 𝜋) is feasible for the dual of the complete master problem. Its objective is 𝑧 𝑅 + 𝑞 𝛾𝑞 , and weak duality proves (28). If 𝑟 𝑞 = 𝑟 𝑞 ≥ −𝜏 for every 𝑞, then (28) is at least 𝑧 𝑅 − |Q|𝜏. Corollary 1 implies that the RMP optimum is attained by a feasible tree, so OPT𝐷 ≤ 𝑧 𝑅 . This proves (29). For a nonoptimal dual feasible Í solution, replace 𝑧 𝑅 by 𝑧 𝐷 = 𝑞 𝛼𝑞 , giving (30). □ Replacing exact costs by their lower bounds gives the recursion ∑︁ (48) 𝑀𝑞→ 𝑝 (𝜎) = min 𝑐 𝑞 (𝜔) + 𝑀𝑟→𝑞 (𝜔| 𝑆𝑟𝑞 ) . 𝜔 ∈Ω𝑞 : 𝜔 | 𝑆𝑞 𝑝 =𝜎 𝑟: {𝑟 ,𝑞 } ∈𝐸 𝑟≠ 𝑝 Here 𝑆 𝑞 𝑝 = 𝐶𝑞 ∩ 𝐶 𝑝 , with an empty minimum equal to +∞. Induction from the leaves identifies each message as the conditional minimum on its component: a fixed configuration fixes the child separators, and 32
running intersection permits addition of the child minima. At the root this evaluates (47); cost monotonicity gives its lower-bound property. Exact costs give (23) and (24). Proof. Proof of Proposition 9. Cost monotonicity gives the lower bound, including infeasible candidate selections. Finite upper costs assemble into a feasible tree by Proposition 5, giving the upper bound. Evaluating that upper objective at 𝑠 − proves (44). If every selected state is exact, a finite feasible selection rules out any selected state of cost +∞; the recovered cost then equals 𝐿. Thus a positive gap requires an unresolved selected state. Exact resolution reduces their finite count, proving the claimed termination bound. □ A further bound applies when 𝜆 𝑣, 𝑓 = 𝜆 > 0. Let OPT𝑑0 denote the optimum among trees of depth at most 𝑑0 < 𝐷, and let 𝐿 𝑑0 ≤ OPT𝑑0 . Every tree of depth greater than 𝑑0 contains at least 𝑑0 + 1 split nodes on one root-to-leaf path. Since its classification error is nonnegative, min{𝐿 𝑑0 , (𝑑0 + 1)𝜆} ≤ OPT𝐷 .
(49)
The two terms cover trees of depth at most 𝑑0 and greater than 𝑑0 , respectively. The D4/D5 computations use 𝑑0 = 2 and the certified lower bound from the matched depth-two problem, giving min{𝐿 2 , 3𝜆}. Proof. Certification and finite termination. The bounds in Proposition 8, (47), and (49) remain valid when combined by their maximum. A feasible incumbent attaining UB satisfies 𝐽 (𝑇) − OPT𝐷 ≤ UB − LB, establishing the stopping certificate. For finite termination, assume exact arithmetic and pricing, no resource limit, and no column deletion. Í With 𝑁 = 𝑞 |Ω𝑞 | and 𝑁0 initial columns, each negative reduced-cost column is absent from the RMP because its current columns have nonnegative reduced costs. Every nonterminal iteration therefore adds a new column, allowing at most 𝑁 − 𝑁0 such iterations. Once exact pricing finds none, the zero-extended dual is feasible for the complete master. The primal is also feasible because all induced rows are retained. Strong duality proves optimality. □ Finite progress with interval costs. Assume finite domains, exact arithmetic, no resource limit or column deletion, and retention of exact costs. Require complete exact pricing and the following progress within finitely many batches whenever the gap is positive: resolve an unresolved state, including proof of infeasibility, or add an absent exact-cost improving column. Each state can be resolved once and each column added once. Once the remaining costs and pricing are exact, a positive gap implies an omitted improving column by Proposition 8. Thus these evaluation and scheduling assumptions give finite termination.
EC.3.4
Conditional-Subtree Bounds
The D4/D5 bounds use weights 1/𝑛, common split penalty 𝜆 ≥ 0, early stopping, unrestricted prediction labels, minimum leaf support, and private depth ℎ = 3. For routed observations 𝑅, define the prediction and conflict losses |𝑅| − max 𝑘 ∈ K |{𝑖 ∈ 𝑅 : 𝑦 𝑖 = 𝑘 }| 𝐸 (𝑅) = , 𝑛 (50) 1 ∑︁ 𝐶 (𝑅) = |𝐺 | − max |{𝑖 ∈ 𝐺 : 𝑦 𝑖 = 𝑘 }| . 𝑛 𝐺 𝑘∈K Groups 𝐺 share identical available-feature vectors and hence follow the same route in every tree, making 𝐶 (𝑅) an error lower bound. For an active subtree with sufficient leaf support and ℎ ≥ 1, the initial lower and upper costs are 𝑉 ℎ0 (𝑅) = min{𝐸 (𝑅), 𝜆 + 𝐶 (𝑅)}, 33
0
𝑉 ℎ (𝑅) = 𝐸 (𝑅).
(51)
Prediction costs 𝐸 (𝑅) and a split costs at least 𝜆 + 𝐶 (𝑅); majority prediction attains the upper bound. At ℎ = 0, both bounds equal 𝐸 (𝑅). Insufficient leaf support makes an active state infeasible, with cost +∞; inactive subtrees cost zero. Let 𝑁 (1) (𝑅) ≥ · · · ≥ 𝑁 (𝐾 ) (𝑅) be the class counts in 𝑅, including zero counts, where 𝐾 = |K |. A subtree with 𝑏 splits has 𝑏 + 1 leaves and can correctly classify observations from at most 𝑏 + 1 distinct classes. The optional bound is ( " #) Í |𝑅| − 𝑏+1 𝑗=1 𝑁 ( 𝑗 ) (𝑅) 𝐵 ℎ (𝑅) = min 𝑏𝜆 + max 𝐶 (𝑅), . (52) 𝑛 0≤𝑏≤min{2ℎ −1,𝐾 −1} The maximum combines two potentially overlapping error bounds. For 𝑏 ≥ 𝐾 − 1, its class-count term is zero and additional splits cannot improve the expression since 𝜆 ≥ 0; the truncated minimum therefore bounds all feasible subtrees. When enabled, use max{𝑉 ℎ0 (𝑅), 𝐵 ℎ (𝑅)}, with ℎ the remaining private depth. For binary classification, 𝐵 ℎ (𝑅) reduces to the initial bound in (51); the class-count bound is therefore enabled by default only for multiclass data. Conditioning the lower-cost messages on root feature 𝑓 gives a valid bound 𝐿 ( 𝑓 ) for trees using that split. If 𝐿( 𝑓 ) ≥ UB, the candidate cannot improve the incumbent, although its states remain in the lower-cost domain.
34
EC.4
Supporting Computational Results
EC.4.1
Individual benchmark results
Table 7 reports per-instance results for the exact methods. Status codes are O (optimal certificate), T (time limit), M (memory limit), and NI (no solver incumbent, with the CART fallback objective reported); dashes denote unavailable entries, including unrun combinations. For JT methods, the relative gap is 100(UB − LB)/max{10−10 , |UB|}; other methods retain their reported gaps. Runtimes shown as 0.00 seconds are positive runtimes below the rounding threshold. CART and HCG are summarized in the main text. Table 7: Individual exact-method results for depths two through five at 𝜆 ∈ {0, 0.01}. 𝐽 includes split penalties; runtime is in seconds. 𝜆=0 Gap Runtime (%) (s) Status
𝐷 Dataset
Method
2 avila
BOCT 0.4746 98.43 DL8.5 0.4664 — GOSDT 0.4664 0.00 MurTree 0.4664 — STreeD 0.4664 0.00 Branches 0.4664 0.00 JT-LP 0.4664 0.00 JT-CG 0.4664 0.00 JT-MP 0.4664 0.00 BOCT 0.0794 0.00 DL8.5 0.0794 — GOSDT 0.0794 0.00 MurTree 0.0794 — STreeD 0.0794 0.00 Branches 0.0794 0.00 JT-LP 0.0794 0.00 JT-CG 0.0794 0.00 JT-MP 0.0794 0.00 BOCT 0.2757 100.00 DL8.5 0.2716 — GOSDT 0.2716 0.00 MurTree 0.2716 — STreeD 0.2716 0.00 Branches 0.2716 0.00 JT-LP 0.2716 0.00 JT-CG 0.2716 0.00 JT-MP 0.2716 0.00 BOCT 0.4349 100.00 DL8.5 0.4294 — GOSDT 0.4294 0.00 MurTree 0.4294 — STreeD 0.4294 0.00 Branches 0.4294 0.00 JT-LP 0.4294 0.00 JT-CG 0.4294 0.00 JT-MP 0.4294 0.00 BOCT 0.3020 100.00 DL8.5 0.2954 — GOSDT 0.2954 0.00 MurTree 0.2954 — STreeD 0.2954 0.00 Branches 0.2954 0.00 JT-LP 0.2954 0.00 JT-CG 0.2954 0.00 JT-MP 0.2954 0.00 BOCT 0.0649 100.00 DL8.5 0.0649 — GOSDT 0.0649 0.00 MurTree 0.0649 — STreeD 0.0649 0.00 Branches 0.0649 0.00 JT-LP 0.0649 0.00
2 banknote
2 compas
2 diabetic
2 diabetic 2 fico
2 give
𝐽
𝜆 = 0.01
600.11 0.32 0.40 0.32 1.00 0.95 0.02 0.01 0.04 59.23 0.01 0.01 0.02 0.88 0.02 0.01 0.00 0.02 600.06 0.09 0.06 0.20 0.90 0.14 0.02 0.01 0.03 667.36 7.59 7.36 4.73 2.85 72.01 0.22 0.13 0.46 606.28 0.35 0.19 0.32 1.00 0.83 0.02 0.01 0.04 600.53 0.53 4.32 1.34 1.40 0.84 0.04
T O O O O O O O O O O O O O O O O O T O O O O O O O O T O O O O O O O O T O O O O O O O O T O O O O O O
𝐽 0.5046 — 0.4964 0.4964 0.4964 0.4964 0.4964 0.4964 0.4964 0.1094 — 0.1094 0.1094 0.1094 0.1094 0.1094 0.1094 0.1094 0.2979 — 0.2953 0.2953 0.2953 0.2953 0.2953 0.2953 0.2953 0.4649 — 0.4452 0.4452 0.4452 0.4452 0.4452 0.4452 0.4452 0.3320 — 0.3173 0.3173 0.3173 0.3173 0.3173 0.3173 0.3173 0.0768 — 0.0668 0.0668 0.0668 0.0668 0.0668
Gap Runtime (%) (s) Status 93.23 — 0.00 — 0.00 0.00 0.00 0.00 0.00 0.00 — 0.00 — 0.00 0.00 0.00 0.00 0.00 91.21 — 0.00 — 0.00 0.00 0.00 0.00 0.00 97.85 — 0.00 — 0.00 0.00 0.00 0.00 0.00 94.94 — 0.00 — 0.00 0.00 0.00 0.00 0.00 79.94 — 0.00 — 0.00 0.00 0.00
600.11 — 0.41 0.32 1.01 1.03 0.02 0.01 0.04 25.10 — 0.01 0.02 0.88 0.02 0.01 0.00 0.02 600.05 — 0.06 0.18 0.91 0.16 0.02 0.01 0.02 600.90 — 9.72 4.28 2.96 110.01 0.21 0.13 0.46 600.23 — 0.19 0.28 0.98 0.85 0.02 0.01 0.03 600.58 — 6.41 1.33 1.50 0.95 0.04
T — O O O O O O O O — O O O O O O O T — O O O O O O O T — O O O O O O O T — O O O O O O O T — O O O O O
Continued on next page
35
Table 7 (continued)
𝜆=0 𝐷 Dataset
Method
𝐽
𝜆 = 0.01
Gap Runtime (%) (s) Status
JT-CG 0.0649 0.00 JT-MP 0.0649 0.00 2 htru2 BOCT 0.0228 100.00 DL8.5 0.0228 — GOSDT 0.0228 0.00 MurTree 0.0228 — STreeD 0.0228 0.00 Branches 0.0228 0.00 JT-LP 0.0228 0.00 JT-CG 0.0228 0.00 JT-MP 0.0228 0.00 2 letter BOCT 0.8794 99.26 DL8.5 0.8558 — GOSDT 0.8558 0.00 MurTree 0.8558 — STreeD 0.8558 0.00 Branches 0.8558 0.00 JT-LP 0.8558 0.00 JT-CG 0.8558 0.00 JT-MP 0.8558 0.00 2 skin BOCT 0.1075 94.32 DL8.5 0.0794 — 2 skin GOSDT 0.0794 0.00 MurTree 0.0794 — STreeD 0.0794 0.00 Branches 0.0794 0.00 JT-LP 0.0794 0.00 JT-CG 0.0794 0.00 JT-MP 0.0794 0.00 2 spambase BOCT 0.1500 97.29 DL8.5 0.1313 — GOSDT 0.1313 0.00 MurTree 0.1313 — STreeD 0.1313 0.00 Branches 0.1313 0.00 JT-LP 0.1313 0.00 JT-CG 0.1313 0.00 JT-MP 0.1313 0.00 2 transactions BOCT 0.0158 100.00 DL8.5 0.0158 — GOSDT 0.0158 0.00 MurTree 0.0158 — STreeD 0.0158 0.00 Branches 0.0158 0.00 JT-LP 0.0158 0.00 JT-CG 0.0158 0.00 JT-MP 0.0158 0.00 3 avila BOCT 0.4553 100.00 DL8.5 0.4270 — GOSDT 0.4270 0.00 MurTree 0.4270 — STreeD 0.4270 0.00 Branches 0.4270 0.00 JT-LP 0.4270 0.00 JT-CG 0.4270 0.00 JT-MP 0.4270 0.00 3 banknote BOCT 0.0219 100.00 DL8.5 0.0219 — GOSDT 0.0219 0.00 MurTree 0.0219 — STreeD 0.0219 0.00 Branches 0.0219 0.00 JT-LP 0.0219 0.00 JT-CG 0.0219 0.00 JT-MP 0.0219 0.00 3 compas BOCT 0.2743 100.00 DL8.5 0.2643 — GOSDT 0.2643 0.00
0.03 0.10 600.08 0.09 0.09 0.22 0.94 0.19 0.01 0.01 0.03 600.11 0.81 1.01 0.39 1.05 1.24 0.04 0.02 0.05 600.74 0.23 0.42 1.21 5.20 0.22 0.03 0.02 0.08 600.10 0.22 0.09 0.17 0.90 0.53 0.01 0.01 0.03 606.75 12.13 22.71 15.26 8.15 17.06 0.57 0.52 1.69 600.15 24.49 52.45 1.19 2.70 35.16 0.44 0.51 0.52 600.03 0.10 0.09 0.02 0.87 0.34 0.01 0.00 0.02 600.15 4.06 4.57
O O T O O O O O O O O T O O O O O O O O T O O O O O O O O T O O O O O O O O T O O O O O O O O T O O O O O O O O T O O O O O O O O T O O
𝐽
Gap Runtime (%) (s) Status
0.0668 0.00 0.0668 0.00 0.0522 61.37 — — 0.0422 0.00 0.0422 — 0.0422 0.00 0.0422 0.00 0.0422 0.00 0.0422 0.00 0.0422 0.00 0.9094 96.69 — — 0.8858 0.00 0.8858 — 0.8858 0.00 0.8858 0.00 0.8858 0.00 0.8858 0.00 0.8858 0.00 0.1375 81.30 — — 0.1060 0.00 0.1060 — 0.1060 0.00 0.1060 0.00 0.1060 0.00 0.1060 0.00 0.1060 0.00 0.1856 85.17 — — 0.1613 0.00 0.1613 — 0.1613 0.00 0.1613 0.00 0.1613 0.00 0.1613 0.00 0.1613 0.00 0.0458 100.00 — — 0.0158 0.00 0.0158 — 0.0158 0.00 0.0158 0.00 0.0158 0.00 0.0158 0.00 0.0158 0.00 0.5253 93.91 — — 0.4832 0.00 0.4832 — 0.4832 0.00 0.4832 0.00 0.4832 0.00 0.4832 0.00 0.4832 0.00 0.0859 53.44 — — 0.0784 0.00 0.0784 — 0.0784 0.00 0.0784 0.00 0.0784 0.00 0.0784 0.00 0.0784 0.00 0.3069 93.48 — — 0.2953 0.00
0.03 0.10 600.10 — 0.07 0.20 0.95 0.22 0.02 0.01 0.03 600.11 — 1.01 0.38 1.08 1.29 0.05 0.02 0.05 600.67 — 0.41 1.12 1.31 0.28 0.03 0.02 0.08 600.13 — 0.08 0.17 0.92 0.52 0.02 0.01 0.02 607.36 — 5.72 30.38 8.93 1.00 0.54 0.50 1.64 600.11 — 47.60 1.19 2.67 25.98 0.44 0.47 0.52 600.02 — 0.07 0.02 0.88 0.25 0.01 0.01 0.02 600.09 — 3.15
O O T — O O O O O O O T — O O O O O O O T — O O O O O O O T — O O O O O O O T — O O O O O O O T — O O O O O O O T — O O O O O O O T — O
Continued on next page
36
Table 7 (continued)
𝜆=0 𝐷 Dataset 3 compas
3 diabetic 3 diabetic
3 fico
3 give
3 htru2
3 letter
3 letter
3 skin
3 skin
3 spambase
Method
𝐽
𝜆 = 0.01
Gap Runtime (%) (s) Status
MurTree 0.2643 — STreeD 0.2643 0.00 Branches 0.2643 0.00 JT-LP 0.2643 0.00 JT-CG 0.2643 0.00 JT-MP 0.2643 0.00 BOCT 0.4319 100.00 DL8.5 0.4253 — GOSDT — — MurTree 0.4253 — STreeD 0.4253 0.00 Branches 0.4263 100.00 JT-LP 0.4253 0.00 JT-CG 0.4253 0.00 JT-MP 0.4253 0.00 BOCT 0.2992 100.00 DL8.5 0.2844 — GOSDT 0.2844 0.00 MurTree 0.2844 — STreeD 0.2844 0.00 Branches 0.2880 100.00 JT-LP 0.2844 0.00 JT-CG 0.2844 0.00 JT-MP 0.2844 0.00 BOCT 0.0644 100.00 DL8.5 0.0644 — GOSDT 0.0644 0.00 MurTree 0.0644 — STreeD 0.0644 0.00 Branches 0.0644 0.00 JT-LP 0.0644 0.00 JT-CG 0.0644 0.00 JT-MP 0.0644 0.00 BOCT 0.0228 100.00 DL8.5 0.0218 — GOSDT 0.0218 0.00 MurTree 0.0218 — STreeD 0.0218 0.00 Branches 0.0218 0.00 JT-LP 0.0218 0.00 JT-CG 0.0218 0.00 JT-MP 0.0218 0.00 BOCT 0.8048 100.00 DL8.5 0.7465 — GOSDT 0.7465 0.00 MurTree 0.7465 — STreeD 0.7465 0.00 Branches 0.7465 0.00 JT-LP 0.7465 0.00 JT-CG 0.7465 0.00 JT-MP 0.7465 0.00 BOCT 0.0520 89.00 DL8.5 0.0394 — GOSDT 0.0394 0.00 MurTree 0.0394 — STreeD 0.0394 0.00 Branches 0.0394 0.00 JT-LP 0.0394 0.00 JT-CG 0.0394 0.00 JT-MP 0.0394 0.00 BOCT 0.1115 99.22 DL8.5 0.0963 — GOSDT 0.0963 0.00 MurTree 0.0963 — STreeD 0.0963 0.00 Branches 0.0963 0.00 JT-LP 0.0963 0.00 JT-CG 0.0963 0.00
0.52 1.00 6.87 0.05 0.02 0.04 601.07 600.19 11.32 20.06 7.14 141.63 8.98 1.95 2.19 600.14 47.18 40.21 1.96 1.74 108.78 0.59 0.18 0.26 600.78 20.68 33.56 3.66 2.53 19.45 0.18 0.09 0.19 600.13 4.63 5.34 0.55 1.04 8.09 0.05 0.03 0.07 600.11 67.17 295.98 2.33 4.85 38.06 0.74 0.56 0.59 602.24 1.53 5.96 1.54 1.56 2.07 0.06 0.04 0.09 600.05 23.91 38.65 1.08 1.04 64.76 0.48 0.09
O O O O O O NI T M O O M O O O T O O O O M O O O T O O O O O O O O T O O O O O O O O T O O O O O O O O T O O O O O O O O T O O O O O O O
𝐽 0.2953 0.2953 0.2953 0.2953 0.2953 0.2953 0.4919 — 0.4452 0.4452 0.4452 0.4452 0.4452 0.4452 0.4452 0.3585 — 0.3173 0.3173 0.3173 0.3173 0.3173 0.3173 0.3173 0.0768 — 0.0668 0.0668 0.0668 0.0668 0.0668 0.0668 0.0668 0.0528 — 0.0422 0.0422 0.0422 0.0422 0.0422 0.0422 0.0422 0.8748 — 0.8165 0.8165 0.8165 0.8165 0.8165 0.8165 0.8165 0.1120 — 0.0894 0.0894 0.0894 0.0894 0.0894 0.0894 0.0894 0.1789 — 0.1521 0.1521 0.1521 0.1521 0.1521 0.1521
Gap Runtime (%) (s) Status — 0.00 0.00 0.00 0.00 0.00 97.97 — 95.50 — 0.00 93.26 0.00 0.00 0.00 96.81 — 0.00 — 0.00 81.02 0.00 0.00 0.00 73.91 — 0.00 — 0.00 0.00 0.00 0.00 0.00 62.12 — 0.00 — 0.00 0.00 0.00 0.00 0.00 96.28 — 0.00 — 0.00 0.00 0.00 0.00 0.00 77.03 — 0.00 — 0.00 0.00 0.00 0.00 0.00 87.35 — 0.00 — 0.00 0.00 0.00 0.00
0.50 1.00 6.54 0.04 0.02 0.04 601.16 — 602.79 19.34 7.70 514.53 8.19 1.31 1.75 600.10 — 34.17 1.92 1.81 68.97 0.59 0.28 0.24 601.36 — 14.07 3.20 2.59 21.21 0.17 0.06 0.16 600.08 — 0.40 0.40 1.00 4.52 0.05 0.02 0.03 600.29 — 152.77 2.55 5.07 44.71 0.76 0.53 0.56 600.73 — 2.56 1.65 1.70 1.97 0.06 0.03 0.09 600.06 — 11.94 1.30 1.07 50.34 0.49 0.07
O O O O O O T — T O O M O O O T — O O O M O O O T — O O O O O O O T — O O O O O O O T — O O O O O O O T — O O O O O O O T — O O O O O O
Continued on next page
37
Table 7 (continued)
𝜆=0 𝐷 Dataset
Method
𝐽
𝜆 = 0.01
Gap Runtime (%) (s) Status
JT-MP 0.0963 0.00 3 transactions BOCT 0.0158 100.00 DL8.5 0.0158 — GOSDT — — MurTree 0.0158 — STreeD 0.0158 0.00 Branches 0.0158 100.00 JT-LP 0.0158 0.00 JT-CG 0.0158 0.00 JT-MP 0.0158 0.00 4 avila BOCT 0.4179 100.00 DL8.5 0.3779 — GOSDT — — MurTree 0.3779 — STreeD 0.3779 0.00 Branches 0.4176 100.00 JT-LP 0.3779 0.00 JT-CG 0.3779 0.00 JT-MP 0.3779 0.00 4 banknote BOCT 0.0219 100.00 DL8.5 0.0066 — GOSDT 0.0066 0.00 MurTree 0.0066 — STreeD 0.0066 0.00 Branches 0.0066 0.00 JT-LP 0.0066 0.00 JT-CG 0.0066 0.00 4 banknote JT-MP 0.0066 0.00 4 compas BOCT 0.2743 100.00 DL8.5 0.2575 — GOSDT 0.2575 0.00 MurTree 0.2575 — STreeD 0.2575 0.00 Branches 0.2650 100.00 4 compas JT-LP 0.2575 0.00 JT-CG 0.2575 0.00 JT-MP 0.2575 0.00 4 diabetic BOCT 0.4261 100.00 DL8.5 0.4331 — GOSDT — — MurTree — — STreeD 0.4212 0.00 Branches 0.4262 100.00 JT-LP 0.4212 0.00 JT-CG 0.4212 0.00 JT-MP 0.4212 0.00 4 fico BOCT 0.2924 100.00 DL8.5 0.2784 — GOSDT — — MurTree 0.2760 — STreeD 0.2760 0.00 Branches 0.2874 100.00 JT-LP 0.2760 0.00 JT-CG 0.2760 0.00 JT-MP 0.2760 0.00 4 give BOCT 0.0642 100.00 DL8.5 0.0637 — GOSDT — — MurTree 0.0636 — STreeD 0.0636 0.00 Branches 0.0668 100.00 JT-LP 0.0636 0.00 JT-CG 0.0636 0.00 JT-MP 0.0636 0.00 4 htru2 BOCT 0.0219 100.00 DL8.5 0.0210 — GOSDT 0.0210 0.00 MurTree 0.0210 —
0.12 605.40 601.13 13.63 104.53 28.30 45.34 5.17 0.91 1.98 600.19 600.03 15.18 50.19 65.93 111.79 1.51 1.57 1.75 600.03 1.12 1.86 0.08 0.90 7.19 0.02 0.10 0.05 600.25 151.06 217.06 14.32 3.92 92.48 0.40 0.68 0.60 601.21 600.27 10.81 604.19 504.89 193.60 212.63 162.33 185.62 600.35 600.02 298.03 187.16 64.70 106.45 3.10 2.75 2.79 603.10 600.18 16.98 89.51 38.53 54.16 0.76 1.40 1.44 600.78 173.90 219.51 13.73
O T T M O O M O O O T T M O O M O O O T O O O O O O O O T O O O O M O O O NI T M T O M O O O T T M O O M O O O T T M O O M O O O T O O O
𝐽
Gap Runtime (%) (s) Status
0.1521 0.00 0.0858 100.00 — — 0.0158 0.00 0.0158 — 0.0158 0.00 0.0158 0.00 0.0158 0.00 0.0158 0.00 0.0158 0.00 0.5479 93.71 — — 0.4780 93.69 0.4749 — 0.4749 0.00 0.4832 83.68 0.4749 0.00 0.4749 0.00 0.4749 0.00 0.1076 66.06 — — 0.0784 0.00 0.0784 — 0.0784 0.00 0.0784 0.00 0.0784 0.00 0.0784 0.00 0.0784 0.00 0.2980 94.75 — — 0.2953 0.00 0.2953 — 0.2953 0.00 0.2953 75.42 0.2953 0.00 0.2953 0.00 0.2953 0.00 0.5361 100.00 — — — — — — 0.4452 0.00 0.4452 93.26 0.4452 0.00 0.4452 0.00 0.4452 0.00 0.4424 95.48 — — — — 0.3173 — 0.3173 0.00 0.3173 81.06 0.3173 0.00 0.3173 0.00 0.3173 0.00 0.0768 85.18 — — 0.0668 0.00 0.0668 — 0.0668 0.00 0.0668 12.71 0.0668 0.00 0.0668 0.00 0.0668 0.00 0.0422 52.65 — — 0.0422 0.00 0.0422 —
0.09 609.06 — 3.48 14.25 8.93 0.98 5.20 0.55 1.75 600.13 — 610.52 64.46 64.82 186.27 1.47 1.46 1.54 600.03 — 1.24 0.14 0.90 2.51 0.03 0.09 0.05 600.09 — 124.58 16.37 3.34 114.10 0.41 0.60 0.56 601.32 — 44.60 603.73 576.20 569.81 209.12 99.12 109.37 600.13 — 344.32 183.42 61.06 122.53 3.05 2.22 2.23 600.53 — 24.71 41.72 22.61 105.30 0.77 1.08 1.01 600.09 — 0.41 1.29
O T — O O O O O O O T — T O O M O O O T — O O O O O O O T — O O O M O O O NI — M T O M O O O T — M O O M O O O T — O O O M O O O T — O O
Continued on next page
38
Table 7 (continued)
𝜆=0 𝐷 Dataset
Method
𝐽
𝜆 = 0.01
Gap Runtime (%) (s) Status
STreeD 0.0210 0.00 Branches 0.0215 100.00 JT-LP 0.0210 0.00 JT-CG 0.0210 0.00 JT-MP 0.0210 0.00 4 letter BOCT 0.6895 100.00 4 letter DL8.5 0.7035 — GOSDT — — MurTree 0.6044 — STreeD 0.6044 0.00 Branches 0.7136 100.00 JT-LP 0.6044 0.00 JT-CG 0.6044 0.00 4 letter JT-MP 0.6044 0.00 4 skin BOCT 0.0264 100.00 DL8.5 0.0173 — GOSDT 0.0173 0.00 MurTree 0.0173 — STreeD 0.0173 0.00 Branches 0.0173 0.00 JT-LP 0.0173 0.00 JT-CG 0.0173 0.00 JT-MP 0.0173 0.00 4 spambase BOCT 0.0930 99.30 DL8.5 0.0859 — GOSDT 0.1300 98.16 MurTree 0.0804 — STreeD 0.0804 0.00 Branches 0.1758 100.00 JT-LP 0.0804 0.00 JT-CG 0.0804 0.00 JT-MP 0.0804 0.00 4 transactions BOCT 0.0158 100.00 DL8.5 0.0158 — GOSDT — — MurTree — — STreeD 0.0158 100.00 Branches 0.0158 100.00 JT-LP 0.0158 0.00 JT-CG 0.0158 0.00 JT-MP 0.0158 0.00 5 avila BOCT 0.3850 100.00 DL8.5 0.3960 — GOSDT — — MurTree — — STreeD 0.3279 100.00 Branches 0.4723 100.00 JT-LP 0.3279 0.00 JT-CG 0.3279 0.00 JT-MP 0.3279 0.00 5 banknote BOCT 0.0102 100.00 DL8.5 0.0000 — GOSDT 0.0000 0.00 5 banknote MurTree 0.0000 — STreeD 0.0000 0.00 Branches 0.0000 0.00 JT-LP 0.0000 0.00 JT-CG 0.0000 0.00 JT-MP 0.0000 0.00 5 compas BOCT 0.2642 100.00 5 compas DL8.5 0.2506 — GOSDT — — MurTree 0.2498 — STreeD 0.2498 0.00 Branches 0.2632 100.00 JT-LP 0.2498 0.00 JT-CG 0.2498 0.00 JT-MP 0.2498 0.00
5.34 43.69 0.42 0.69 0.60 600.21 600.03 17.99 120.63 172.82 122.11 5.11 2.62 3.42 600.96 11.29 45.63 6.45 4.67 20.51 0.32 0.80 0.70 600.06 600.01 606.09 70.92 10.48 93.12 1.87 1.72 1.96 609.53 601.87 12.62 613.27 600.00 36.42 77.80 51.81 59.79 600.95 600.03 14.63 599.71 599.06 97.23 77.76 54.12 79.44 600.04 2.21 20.42 0.14 0.90 25.22 0.20 0.29 0.04 600.28 600.02 152.61 325.91 67.81 92.68 6.41 9.23 8.49
O M O O O T T M O O M O O O T O O O O O O O O T T T O O M O O O T T M T T M O O O T T M T T M O O O T O O O O O O O O T T M O O M O O O
𝐽
Gap Runtime (%) (s) Status
0.0422 0.00 0.0422 0.00 0.0422 0.00 0.0422 0.00 0.0422 0.00 0.8396 96.25 — — 0.8877 96.61 0.7529 — 0.7529 0.00 0.8192 91.02 0.7529 0.00 0.7529 0.00 0.7529 0.00 0.1464 100.00 — — 0.0861 0.00 0.0861 — 0.0861 0.00 0.0861 0.00 0.0861 0.00 0.0861 0.00 0.0861 0.00 0.2217 89.78 — — 0.1791 87.38 0.1489 — 0.1489 0.00 0.1528 64.58 0.1489 0.00 0.1489 0.00 0.1489 0.00 0.1658 100.00 — — 0.0158 0.00 0.0158 — 0.0158 0.00 0.0158 0.00 0.0158 0.00 0.0158 0.00 0.0158 0.00 0.6150 94.42 — — — — — — 0.4749 100.00 0.4832 83.81 0.4749 0.00 0.4749 0.00 0.4749 0.00 0.1294 75.05 — — 0.0784 0.00 0.0784 — 0.0784 0.00 0.0784 0.00 0.0784 0.00 0.0784 0.00 0.0784 0.00 0.2980 95.19 — — — — 0.2953 — 0.2953 0.00 0.2953 76.13 0.2953 0.00 0.2953 0.00 0.2953 0.00
1.00 15.95 0.39 0.55 0.48 600.17 — 643.88 151.59 204.25 199.00 5.38 2.68 3.21 601.01 — 23.00 8.02 5.79 24.68 0.34 0.71 0.68 600.48 — 606.93 100.24 10.26 175.76 1.83 1.26 1.29 610.26 — 3.59 15.03 8.94 0.94 76.71 0.20 0.41 600.13 — 116.24 599.95 599.86 200.96 77.72 39.61 51.09 600.03 — 10.10 0.80 1.18 14.40 0.23 0.65 0.41 600.14 — 207.23 414.00 54.25 127.06 6.55 6.50 4.99
O O O O O T — T O O M O O O NI — O O O O O O O T — T O O M O O O T — O O O O O O O T — M T T M O O O T — O O O O O O O T — M O O M O O O
Continued on next page
39
Table 7 (continued)
𝜆=0 𝐷 Dataset 5 diabetic
Method
𝐽
𝜆 = 0.01
Gap Runtime (%) (s) Status
BOCT 0.4254 100.00 DL8.5 0.4323 — GOSDT — — MurTree — — STreeD 0.4609 100.00 Branches 0.4262 100.00 JT-LP 0.4252 100.00 JT-CG 0.4184 99.99 JT-MP 0.4168 99.99 5 fico BOCT 0.2810 100.00 DL8.5 0.2784 — GOSDT — — MurTree — — STreeD 0.2658 100.00 Branches 0.3016 100.00 JT-LP 0.2649 0.00 JT-CG 0.2649 0.00 JT-MP 0.2649 0.00 5 give BOCT 0.0637 100.00 DL8.5 0.0635 — GOSDT — — MurTree — — STreeD 0.0668 100.00 Branches 0.0668 100.00 JT-LP 0.0629 0.00 JT-CG 0.0629 0.00 JT-MP 0.0629 0.00 5 htru2 BOCT 0.0213 100.00 DL8.5 0.0200 — GOSDT — — MurTree 0.0197 — STreeD 0.0197 0.00 5 htru2 Branches 0.0217 100.00 JT-LP 0.0197 0.00 JT-CG 0.0197 0.00 JT-MP 0.0197 0.00 5 letter BOCT 0.5477 100.00 DL8.5 0.7575 — GOSDT — — 5 letter MurTree — — STreeD 0.4854 100.00 Branches 0.8219 100.00 JT-LP 0.4425 0.00 JT-CG 0.4425 0.00 JT-MP 0.4425 0.00 5 skin BOCT 0.0239 100.00 DL8.5 0.0115 — GOSDT 0.0115 0.00 MurTree 0.0115 — STreeD 0.0115 0.00 Branches 0.0225 100.00 JT-LP 0.0115 0.00 JT-CG 0.0115 0.00 JT-MP 0.0115 0.00 5 spambase BOCT 0.0826 99.47 DL8.5 0.2630 — GOSDT — — MurTree — — STreeD 0.0635 0.00 Branches 0.1756 100.00 JT-LP 0.0635 0.00 JT-CG 0.0635 0.00 JT-MP 0.0635 0.00 5 transactions BOCT 0.0158 100.00 DL8.5 0.0158 — GOSDT — — MurTree — — STreeD 0.0158 100.00
601.75 600.20 11.05 604.02 600.00 95.64 600.28 610.03 599.99 600.80 600.02 68.69 599.48 599.74 100.93 348.02 256.61 300.96 603.26 600.25 16.70 600.66 600.00 46.94 19.96 29.30 36.25 601.32 600.03 128.24 240.39 78.37 91.39 5.58 8.17 6.74 601.67 600.04 16.42 599.52 599.19 108.09 358.86 76.28 118.59 600.96 132.51 289.17 32.89 27.90 39.60 0.78 2.03 2.02 600.31 600.01 76.62 599.42 418.99 148.54 181.97 123.05 171.02 611.48 601.96 12.59 613.20 600.00
T T M T T M T T T T T M T T M O O O NI T M T T M O O O T T M O O M O O O T T M T T M O O O NI O O O O M O O O T T M T O M O O O T T M T T
𝐽
Gap Runtime (%) (s) Status
0.6354 100.00 — — — — — — 0.4609 100.00 0.4452 93.26 0.4452 100.00 0.4452 91.00 0.4452 91.01 0.3568 95.80 — — — — — — 0.3173 100.00 0.3173 81.06 0.3173 0.00 0.3173 0.00 0.3173 0.00 0.3737 100.00 — — 0.0668 0.00 0.0668 — 0.0668 0.00 0.0668 13.83 0.0668 0.00 0.0668 0.00 0.0668 0.00 0.0422 52.38 — — 0.0422 0.00 0.0422 — 0.0422 0.00 0.0422 0.00 0.0422 0.00 0.0422 0.00 0.0422 0.00 0.8578 96.36 — — — — — — 0.7417 100.00 0.8192 91.19 0.7111 0.00 0.7111 0.00 0.7111 0.00 0.2239 100.00 — — 0.0861 0.00 0.0861 — 0.0861 0.00 0.0861 18.71 0.0861 0.00 0.0861 0.00 0.0861 0.00 0.2217 90.15 — — — — — — 0.1469 0.00 0.1528 65.00 0.1469 0.00 0.1469 0.00 0.1469 0.00 0.3158 100.00 — — 0.0158 0.00 0.0158 — 0.0158 0.00
602.09 — 43.33 603.66 600.00 572.46 600.44 606.44 599.99 600.49 — 70.48 599.51 599.96 128.88 349.30 156.38 173.08 600.64 — 23.56 443.75 174.18 117.52 19.43 11.06 11.97 600.13 — 0.40 1.27 1.01 19.10 5.53 1.11 0.94 600.16 — 134.85 599.66 599.45 201.24 357.08 69.44 103.36 600.54 — 99.12 34.70 29.65 55.16 0.75 1.71 1.56 600.28 — 89.44 599.44 448.60 175.87 182.60 75.93 71.81 611.66 — 3.40 14.34 9.00
T — M T T M T T T T — M T T M O O O NI — O O O M O O O T — O O O O O O O T — M T T M O O O NI — O O O M O O O T — M T O M O O O T — O O O
Continued on next page
40
Table 7 (continued)
𝜆=0 𝐷 Dataset
Method
𝐽
𝜆 = 0.01
Gap Runtime (%) (s) Status
Branches 0.0158 100.00 JT-LP 0.0158 100.00 JT-CG 0.0158 99.92 JT-MP 0.0157 99.92
23.81 621.06 601.47 600.53
41
M T T T
𝐽
Gap Runtime (%) (s) Status
0.0158 0.00 0.0158 100.00 0.0158 0.00 0.0158 0.00
0.94 611.95 0.20 0.39
O T O O
EC.4.2
Unresolved deep settings
Table 8: Settings not certified by both JT-CG and STreeD within 600 seconds. Bounds are JT-CG bounds unless marked otherwise. Dataset
𝐷
𝜆
JT-CG status
JT-CG bound/optimum
STreeD status
avila avila diabetic diabetic fico fico give letter letter transactions transactions
5 5 5 5 5 5 5 5 5 4 5
0 .01 0 .01 0 .01 0 0 .01 0 0
O O T T O O O O O O T
0.327886 0.474929 [0.000029, 0.418372] [0.040069, 0.445204] 0.264939 0.317256 0.062947 0.442500 0.711100 0.015771 [0.000013, 0.015756]
T T T T T T T T T T T
Figure 5 traces the three uncertified JT-CG settings. The final feasible objectives are first obtained within 3.5 seconds. Subsequent evaluation neither improves these incumbents nor closes the gap; the final lower bounds remain well below the corresponding upper bounds in Table 8. Diabetic, λ = 0
Diabetic, λ = 0.01
0.4
Transactions, λ = 0 0.0150
0.4
Objective bound
0.0125 0.3
0.3 Feasible upper bound Lower bound
0.2
0.0100 0.0075
0.2
0.0050 0.1
0.1
0.0
0.0 0
200
400 Runtime (s)
600
0.0025 0.0000 0
200
400 Runtime (s)
600
0
200
400
600
Runtime (s)
Figure 5: Observed lower bounds and feasible upper bounds for the three uncertified JT-CG settings. Curves show recorded updates only.
42