Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound

Catalin E. Brita; Emir Demirovi\'c; Jacobus G. M. van der Linden

REVIEW 3 major objections 5 minor 57 references

Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound

T0 review · 3 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read ConTree computes exactly optimal classification trees directly on continuous features, without binarization, and does so orders of magnitude faster than prior exact methods, reaching depth four on real-world datasets.

desk verdict Strong practical contribution, but Algorithm 2 as written does not compute the stated objective for multiclass data, which undermines the optimality claims until fixed. read the letter →

arxiv 2501.07903 v1 pith:5TA2TN3N submitted 2025-01-14 cs.LG cs.AIcs.DS

Catalin E. Brita , Jacobus G. M. van der Linden , Emir Demirović This is my paper · ORCID

classification cs.LGcs.AIcs.DS

keywords optimaldecisiontreescontinuousfeaturesdynamicprogrammingbranch-and-boundsimilaritylowerboundpruningexactoptimizationexplainableAI

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper introduces ConTree, an algorithm for computing exactly optimal classification trees—trees that minimize misclassification on the training data for a fixed depth limit—directly on continuous feature data, avoiding the coarse binarization that prior optimal methods relied on. The central claim is a combination of correctness and scalability: new pruning rules derived from a similarity-based lower bound, evaluated in constant time using the sorted order of feature values, make exact search practical at depths that previously timed out. The paper reports that ConTree outperforms the leading continuous-feature exact method by an average factor of 63 at depth three, reaches provably optimal depth-four trees on the benchmark set, and improves test accuracy by roughly 5% over CART at the same depth. A sympathetic reader would take away that exact, explainable trees are no longer confined to binarized or small data.

What carries the argument

The load-bearing mechanism is the similarity-based lower bound (SLB), $\theta(D_{\text{new}}) \ge \theta(D_{\text{old}}) - |D_{\text{old}} \setminus D_{\text{new}}|$, applied to continuous splits through sorted feature indices. For two thresholds $\tau$ and $\tau'$, the number of observations that shift between the left and right subproblems is exactly $|z(\tau)-z(\tau')|$, the difference of the split indices in the sorted feature column, so the bound costs $O(1)$ rather than the $O(n)$ scan used by prior SLB implementations. This index-difference bound powers three pruning rules: neighborhood pruning deletes thresholds within distance $\Delta$ of an evaluated split, interval shrinking tightens candidate intervals using neighboring computed splits and zero-error subtrees, and sub-interval pruning discards whole index intervals when a left-solution/right-solution pair already exceeds the current upper bound. The depth-two subroutine $D2Split$ carries the rest of the speedup: for a fixed root split it traverses the sorted data once per candidate second-level feature, maintaining per-class counts for all four leaves, and returns optimal subtree errors in $O(|D||F|)$.

What would settle it

Run ConTree with max-gap=0 on a small continuous dataset (e.g., 200 points) and compare its training misclassification to a brute-force enumeration of all binary axis-aligned trees up to the same depth; any discrepancy would show a pruning rule discarded the optimal split. The direct target is Theorem 1: search over all pairs of thresholds $\tau, \tau'$ for a case where the optimal score at $\tau'$ is more than $|z(\tau)-z(\tau')|$ below that at $\tau$.

Watch

Extended reading notes

Core claim

ConTree's contribution is an exact dynamic-programming and branch-and-bound search in which the continuous nature of features is an asset rather than a burden. Because the data are sorted per feature, the difference between two candidate split thresholds is just the difference of their split indices, $|z(\tau)-z(\tau')|$, and this index difference plugs directly into the similarity-based lower bound $\theta_{D_{\text{new}}} \ge \theta_{D_{\text{old}}} - |D_{\text{old}}\setminus D_{\text{new}}|$. That gives three provably safe pruning rules—neighborhood pruning, interval shrinking, and sub-interval pruning—which together eliminate the vast majority of candidate splits while preserving the optimal tree. A specialized depth-two subroutine solves both subtrees of a depth-two node in $O(|D||F|)$ by a single sorted traversal with incremental class counts. On 16 UCI datasets, ConTree solves depth-two trees in the sub-second to second range, is on average 63 times faster than Quant-BnB at depth three, computes optimal depth-four trees for twelve of sixteen datasets within four hours, and uses megabytes of memory where Quant-BnB used gigabytes.

Load-bearing premise

The pruning rules stand on the claim that moving observations from one side of a split to the other cannot reduce the optimal misclassification score by more than the number of observations moved, a bound stated in Theorem 1 whose proof as written omits the monotonicity step on the growing side.

Editorial extensions

If this is right

Exact optimal decision trees become feasible at depth four and beyond on datasets with tens of thousands of instances, so provably optimal explainable models can replace greedy heuristics in applications where interpretability matters.
Training directly on all possible thresholds, rather than a binarized subset, yields higher out-of-sample accuracy: roughly 5% better than CART and 0.7–1.0% better than optimal trees trained on binarized features at the same depth.
The max-gap parameter offers a principled runtime-accuracy trade-off: allowing a small optimality gap cuts training time dramatically, enabling even deeper trees or larger datasets within the same budget.
The pruning rules are independent of the specific dataset and could be reused in other dynamic-programming solvers for optimal decision trees, including variants with node costs or regression objectives.
The memory footprint (megabytes) is small enough that ConTree runs on commodity hardware, removing a barrier to deploying exact tree search in practice.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The index-difference trick suggests a general template for nested partitions of sorted sequences: the optimal loss of any partition model (regression trees, survival trees, rule lists) cannot drop by more than the number of items that cross a cut, so the same O(1) lower-bound pruning may transfer to those objectives.
The depth-two subroutine's inner loops are independent per feature, so the algorithm is a natural candidate for SIMD or GPU acceleration; the reported runtimes are single-threaded C++.
ConTree's anytime curves show the optimal solution is usually found early, so a better split-evaluation order or heuristic warm start could shrink the time-to-best even when the time-to-proof remains the bottleneck.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's the short version: ConTree is a serious engineering contribution to optimal decision trees on continuous features, but the paper as written has a load-bearing bug in Algorithm 2 for multiclass datasets. If the pseudocode matches the implementation, the claimed optimality guarantees don't hold for the datasets with |Y|>2.

What's genuinely new: applying the similarity lower bound to sorted continuous features with O(1) index differences, the three pruning rules, and an O(|D||F|) depth-two subroutine that avoids the quadratic memory of MurTree's approach. The experiments are broad — 16 UCI datasets, comparisons to MIP/SAT/Quant-BnB, memory tables, depth five and six results. The speedups over Quant-BnB are large and the memory footprint is impressively small. The ablation showing SP prunes 99.6% of D2Split calls is convincing evidence the pruning machinery works.

The soft spots, in order. First, and most important: Algorithm 2 defines θLL ← min_ŷ C^ŷ_L and θLR ← min_ŷ (FQ^ŷ_L − C^ŷ_L). That is the minimum class count, not the misclassification error. For a leaf with counts (5,5,1), min is 1 but the true error is 6; for (2,2,2), min is 2 but the error is 4. The two expressions agree only for binary data. Because D2Split is the base case for every recursive call at depth two, an underestimated subtree score can set the upper bound below the true optimum and prune away the optimal split. This directly threatens the central claim of provable optimality on multiclass data — which includes several of the sixteen evaluated datasets.

Second, Theorem 1's proof as written cites the wrong set difference. The theorem is salvageable with a side-wise argument that applies Eq. (3) to the shrinking side and monotonicity to the growing side, but as printed it is not a direct application of the bound. Not fatal, but it should be rewritten.

Third, Algorithm 1 has undefined first-iteration values (B is called on an empty V) and the text of Corollary 1 omits the max(1, ...) floor that appears in the algorithm. These are presentation issues, but they make reproduction harder than it should be.

Fourth, no runtime variance is reported despite averages over twenty runs, and the repo is not pinned to a commit. For a paper whose headline is orders-of-magnitude speedups, a commit hash and variance numbers would help independent verification.

Who this is for: researchers in interpretable ML and anyone using optimal decision trees on numeric data. It deserves a serious referee because the core ideas are strong and the empirical gains are large, but the multiclass bug needs to be fixed and the experiments rerun (or the claims scoped to binary data) before the optimality claims can be trusted. My recommendation: send to peer review as conditional, require the authors to correct Algorithm 2, provide a correctness proof for D2Split, pin the code, and report variance.

Referee Report

3 major / 5 minor

Summary. The paper introduces ConTree, a dynamic-programming branch-and-bound algorithm for computing optimal classification trees directly on continuous feature data without binarization. The main contributions are three similarity-based pruning techniques (neighborhood pruning, interval shrinking, sub-interval pruning) that exploit sorted feature values, and a specialized depth-two subroutine D2Split. The authors report speedups of one or more orders of magnitude over Quant-BnB and other MIP/SAT baselines, and they claim to be the first to compute depth-four optimal trees on datasets of moderate size. The paper provides a recursive DP formulation, three pruning theorems, pseudocode, and experiments on 16 UCI datasets.

Significance. If the algorithm were correct as stated, it would be a valuable practical advance for optimal decision trees with numeric features, combining strong pruning with low memory use and reproducible open-source code. The pruning ideas are natural and the experimental comparison is broad. However, the depth-two subroutine, which is the base case for all recursions, computes the wrong objective for multiclass datasets, so the central optimality guarantee does not hold for the multiclass experiments. The three pruning theorems appear plausible, though Theorem 1's proof is not written correctly. Because the core algorithmic framework is sound and the subroutine error is localized and fixable, the paper warrants major revision rather than rejection, but the experimental claims and optimality statements must be revisited.

major comments (3)

[Algorithm 2] The depth-two subroutine is incorrect for multiclass data. In Algorithm 2, the lines θLL ← min_ŷ(C^ŷ_L) and θLR ← min_ŷ(FQ^ŷ_L − C^ŷ_L) compute the minimum class count in each leaf, not the misclassification count. For a leaf with class counts n_y, the true error is Σ_y n_y − max_y n_y; these two expressions agree only for binary labels. For example, with counts (5,5,1), min = 1 while the true error is 6; with (2,2,2), min = 2 while the true error is 4. Because Algorithm 1 uses θw,L and θw,R returned by D2Split to update U B and θopt, and then prunes using these values, an underestimated subtree score can set U B below the true optimum and prune away the optimal split. This affects all datasets with |Y|>2 (e.g., Avila, Bean, Fault, Page, Room, Segment, Skin, Wilt) and propagates to the depth-three and depth-four results that use D2Split as their base case. The paper provides no proof that D2Split minimizes Eq. (2). The pseudocode must be corrected to use total−max counts, and the optimality claim must be re-verified, ideally by independent validation on small multiclass instances.
[Theorem 1] The proof of Theorem 1 cites the wrong set difference for the similarity lower bound. In the case τ′ > τ, the proof states |D(f ≤ τ′) \ D(f ≤ τ)| = z(τ′) − z(τ) and then applies Eq. (3). But Eq. (3) lower-bounds the error of the new dataset in terms of an old dataset from which points are removed: θ(Dnew) ≥ θ(Dold) − |Dold \ Dnew|. Taking Dold = D(f≤τ′) and Dnew = D(f≤τ) gives the opposite direction from what is claimed. The theorem is nevertheless true: for τ′ > τ, the left dataset grows (so its optimal error is monotone non-decreasing), while the right dataset shrinks and the SLB can be applied to it; a similar argument handles τ′ < τ. The proof needs to be rewritten to make this side-wise argument explicit; as written, it does not establish the stated inequality.
[Algorithm 1] Algorithm 1 is not well-defined on the first iteration because V is initialized to the empty set and B([i..j], V) is called immediately. The function B returns max u ∈ V : u < i and min v ∈ V : v > j, both of which are undefined when V is empty. The pseudocode should specify initial values (e.g., u = 0, v = m+1) and should skip the interval shrinking and sub-interval pruning steps that depend on θu and θv until at least one split has been evaluated. In addition, the line Δu ← θu − U B omits the max(1, ·) floor stated in Corollary 1; without it, the pruning distance can be zero or negative when θu = U B, which is inconsistent with the corollary.

minor comments (5)

[Section 4] The example feature vector [0.4, 0.5, 0.5, 0.7, 0.8, 0.10] is not sorted; 0.10 appears to be a typo for 1.0 or another value. The example should be corrected to maintain consistency with the surrounding argument.
[Eq. (7)-(8)] The two helper functions in Eqs. (7) and (8) are both typeset as ¯A, which makes it difficult to distinguish the upper and lower threshold functions. Please use distinct symbols such as A_upper and A_lower, or add an explicit description in the text.
[Algorithm 2] The pseudocode line 'Same logic for instances going right' leaves the right-subtree updates unspecified. For reproducibility, the θRL and θRR computations should be written out explicitly.
[Algorithm 1] The updates ML ← w+1 and MR ← w−1 should be ML ← max(ML, w+1) and MR ← min(MR, w−1). As written, they may overwrite a previously found bound with a weaker one if the search later evaluates a split point inside the already-established zero-error region.
[Algorithm 1] The text says η is the length of the longest side of the interval edges, but the pseudocode computes η ← min(z(w) − z(i), z(j) − z(w)), which is the shortest side. The mismatch should be resolved either in the text or in the code; while using the shorter side only weakens the upper bound (and thus does not harm optimality), the inconsistency is confusing.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: ConTree's optimality and runtime claims rest on the external SLB bound and controlled experiments, not on fitted inputs or self-referential definitions.

full rationale

The central derivation is self-contained relative to an external lower bound. The pruning theorems (Theorems 1-3) are derived from Eq. (3), the similarity lower bound credited to Hu/Rudin/Seltzer, Lin et al., and Demirović et al.; Eq. (3) is an independent inequality and is not assumed to equal the paper's speedup results. The recursive DP formulation (Eqs. 4-6) is a standard decomposition, and the branch-and-bound upper bounds are computed from actual subtree solutions rather than from the claimed output. The experimental speedups over Quant-BnB and MIP/SAT methods are empirical comparisons, not predictions forced by fitted parameters. Self-citations to Demirović et al. (2022) supply caching and the earlier depth-two-subroutine idea, but they do not carry the new continuous-feature pruning claims; removing them would not collapse the derivation. The depth-two subroutine's use of min-class-count in place of misclassification error for multiclass leaves and the compressed proof of Theorem 1 are correctness/rigor concerns, not circularity: they do not make any output equal to its input by definition.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

No new physical or structural entities are introduced; the algorithm is a search procedure. The free parameters are user-scalable knobs (max-gap) and a preprocessing tolerance (epsilon), not fitted constants. The central claim rests on the cited similarity lower bound and standard monotonicity of the misclassification objective.

free parameters (2)

max-gap = 0 (default)
User-specified optimality gap; when greater than zero, the solution may be up to max-gap misclassifications from optimal. Not used in the optimal experiments, where it is set to 0.
epsilon for unique value detection = 1e-7
Used in preprocessing to determine unique feature values (Appendix A). It defines which values are considered equal and therefore affects the candidate threshold set.

assumptions (3)

domain assumption Similarity lower bound (Eq. 3): theta(Dnew) >= theta(Dold) - |Dold without Dnew| for the same depth limit
Taken from Hu et al. 2019, Lin et al. 2020, and Demirovic et al. 2022; used for all three pruning techniques in Theorems 1 to 3.
domain assumption An optimal threshold can be restricted to midpoints between consecutive unique feature values (Eq. 1)
Standard for axis-aligned trees on numeric data; this defines the search space S^f and is used without proof.
standard math Misclassification score is monotone non-decreasing when adding observations to a dataset
Used implicitly in Theorem 2 and Theorem 3: larger subproblems have greater or equal optimal loss.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound." pith.science (2026). https://pith.science/paper/5TA2TN3N

@misc{pith2026250107903,
  author       = {Pith},
  title        = {Pith review of: Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5TA2TN3N}},
  note         = {Machine review of arXiv:2501.07903}
}

read the original abstract

Computing an optimal classification tree that provably maximizes training performance within a given size limit, is NP-hard, and in practice, most state-of-the-art methods do not scale beyond computing optimal trees of depth three. Therefore, most methods rely on a coarse binarization of continuous features to maintain scalability. We propose a novel algorithm that optimizes trees directly on the continuous feature data using dynamic programming with branch-and-bound. We develop new pruning techniques that eliminate many sub-optimal splits in the search when similar to previously computed splits and we provide an efficient subroutine for computing optimal depth-two trees. Our experiments demonstrate that these techniques improve runtime by one or more orders of magnitude over state-of-the-art optimal methods and improve test accuracy by 5% over greedy heuristics.

Figures

Figures reproduced from arXiv: 2501.07903 by the authors.

**Figure 1.** The split points u and v for which the score θu and θv are calculated are yellow. The newly pruned values are shown in red. Green indicates the remaining split points for further search. Blue indicates unaffected values outside of [i..j]. Leaf nodes assign the label with the least misclassifications. Branching nodes find the feature f with the best misclassification score from the subtrees by calling the subprocedu… view at source ↗

**Figure 2.** The number of D2Split calls for no pruning, the three pruning techniques, and all three combined. routine D2Split versus without (ConTree with “No D2”) for computing depth-two trees. Both methods use all the pruning techniques. Averaged over twenty runs, the depth-two solver improves the computation time by a factor of 320 compared to the baseline (geometric mean). Runtime Mazumder, Meng, and Wang (2022) compared Q… view at source ↗

**Figure 3.** The distance to the optimal solution for ConTree’s [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

57 extracted references · 53 canonical work pages

[1]

, " * write output.state after.block = add.period write newline

ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...
[2]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...
[3]

Aghaei, S.; G \' o mez, A.; and Vayanos, P. 2024. Strong Optimal Classification Trees . Operations Research

work page 2024
[4]

Aglin, G.; Nijssen, S.; and Schaus, P. 2020 a . Learning Optimal Decision Trees Using Caching Branch-and-Bound Search . In Proceedings of AAAI-20, 3146--3153

work page 2020
[5]

Aglin, G.; Nijssen, S.; and Schaus, P. 2020 b . PyDL8.5: a Library for Learning Optimal Decision Trees . In Proceedings of IJCAI-20, 5222--5224

work page 2020
[6]

Al \` e s, Z.; Hur \' e , V.; and Lambert, A. 2024. New optimization models for optimal classification trees . Computers & Operations Research , 164: 106515

work page 2024
[7]

Al \` o s, J.; Ans \' o tegui, C.; and Torres, E. 2023. Interpretable decision trees through MaxSAT . Artificial Intelligence Review, 56(8): 8303--8323

work page 2023
[8]

B.; D \' i az-Rodr \' i guez, N.; Del Ser, J.; Bennetot, A.; Tabik, S.; Barbado, A.; Garc \' i a, S.; Gil-L \' o pez, S.; Molina, D.; Benjamins, R.; Chatila, R.; and Herrera, F

Arrieta, A. B.; D \' i az-Rodr \' i guez, N.; Del Ser, J.; Bennetot, A.; Tabik, S.; Barbado, A.; Garc \' i a, S.; Gil-L \' o pez, S.; Molina, D.; Benjamins, R.; Chatila, R.; and Herrera, F. 2020. Explainable Artificial Intelligence (XAI): Concepts, taxonomies, opportunities and challenges toward responsible AI . Information Fusion, 58: 82--115

work page 2020

Show all 57 references

[9]

Avellaneda, F. 2020. Efficient Inference of Optimal Decision Trees . In Proceedings of AAAI-20, 3195--3202

2020
[10]

Bertsimas, D.; and Dunn, J. 2017. Optimal classification trees . Machine Learning, 106(7): 1039--1082

2017
[11]

Bhatt, R.; and Dhall, A. 2012. Skin Segmentation Dataset . UCI Machine Learning Repository

2012
[12]

Bock, R. 2007. MAGIC Gamma Telescope Dataset . UCI Machine Learning Repository

2007
[13]

H.; Olshen, R

Breiman, L.; Friedman, J. H.; Olshen, R. A.; and Stone, C. J. 1984. Classification and Regression Trees . Monterey, CA: Wadsworth and Brooks

1984
[14]

Brodley, C. 1990. Image Segmentation Dataset . UCI Machine Learning Repository

1990
[15]

Buscema, M.; Terzi, S.; and Tastle, W. 2010. Steel Plates Faults Dataset . UCI Machine Learning Repository

2010
[16]

Candanedo, L. M. I.; and Feldheim, V. 2016. Accurate occupancy detection of an office room from light, temperature, humidity and CO2 measurements using statistical learning models. Energy and Buildings, 112: 28--39

2016
[17]

Cinar, I.; and Koklu, M. 2019. Classification of rice varieties using artificial intelligence methods. International Journal of Intelligent Systems and Applications in Engineering, 7(3): 188--194

2019
[18]

C nar, \.I .; Koklu, M.; and Ta s demir, S . 2020. Classification of raisin grains using machine vision and artificial intelligence methods. Gazi Journal of Engineering Sciences, 6(3): 200--209

2020
[19]

G.; and Pedreira, C

Costa, V. G.; and Pedreira, C. E. 2023. Recent Advances in Decision Trees: An Updated Survey . Artificial Intelligence Review, 56: 4765--4800

2023
[20]

Demirovi \' c , E.; Hebrard, E.; and Jean, L. 2023. Blossom: an Anytime Algorithm for Computing Optimal Decision Trees . In Proceedings of ICML-23, 7533--7562

2023
[21]

Demirovi \' c , E.; Lukina, A.; Hebrard, E.; Chan, J.; Bailey, J.; Leckie, C.; Ramamohanarao, K.; and Stuckey, P. J. 2022. MurTree: Optimal Classification Trees via Dynamic Programming and Search . Journal of Machine Learning Research, 23(26): 1--47

2022
[22]

Dua, D.; and Graff, C. 2017. UCI Machine Learning Repository

2017
[23]

eBay . 2020. Shill Bidding Dataset . UCI Machine Learning Repository

2020
[24]

G \" u nl \" u k, O.; Kalagnanam, J.; Li, M.; Menickelly, M.; and Scheinberg, K. 2021. Optimal Decision Trees for Categorical Data via Integer Programming . Journal of Global Optimization, 81: 233--260

2021
[25]

Hu, H.; Siala, M.; Hebrard, E.; and Huguet, M.-J. 2020. Learning Optimal Decision Trees with MaxSAT and its Integration in AdaBoost . In IJCAI-PRICAI 2020, 1170--1176

2020
[26]

Hu, X.; Rudin, C.; and Seltzer, M. 2019. Optimal Sparse Decision Trees . In Advances in NeurIPS-19, 7267--7275

2019
[27]

Hua, K.; Ren, J.; and Cao, Y. 2022. A Scalable Deterministic Global Optimization Algorithm for Training Optimal Decision Tree . In Advances in NeurIPS-22, 8347--8359

2022
[28]

Hyafil, L.; and Rivest, R. L. 1976. Constructing optimal binary decision trees is NP-complete . Information processing letters, 5(1): 15--17

1976
[29]

Janota, M.; and Morgado, A. 2020. SAT-Based Encodings for Optimal Decision Trees with Explicit Paths . In Proceedings of the International Conference on Theory and Applications of Satisfiability Testing (SAT 2020), 501--518

2020
[30]

Johnson, B. 2014. Wilt Dataset . UCI Machine Learning Repository

2014
[31]

Kiossou, H.; Schaus, P.; Nijssen, S.; and Houndji, V. R. 2022. Time constrained DL8.5 using Limited Discrepancy Search . In Proceedings of ECML-PKDD-22, 443--459

2022
[32]

Koklu, M.; and Ozkan, I. A. 2020. Multiclass classification of dry beans using computer vision and machine learning techniques. Computers and Electronics in Agriculture, 174: 105507

2020
[33]

Lin, J.; Zhong, C.; Hu, D.; Rudin, C.; and Seltzer, M. 2020. Generalized and Scalable Optimal Sparse Decision Trees . In Proceedings of ICML-20, 6150--6160

2020
[34]

T.; and Hermes, C

Liu, E.; Hu, T.; Allen, T. T.; and Hermes, C. 2024. Optimal classification trees with leaf-branch and binary constraints . Computers & Operations Research , 166: 106629

2024
[35]

Lohweg, V. 2013. Banknote Authentication Dataset . UCI Machine Learning Repository

2013
[36]

J.; Stappers, B

Lyon, R. J.; Stappers, B. W.; Cooper, S.; Brooke, J. M.; and Knowles, J. D. 2016. Fifty years of pulsar candidate selection: from simple filters to a new principled real-time classification approach . Monthly Notices of the Royal Astronomical Society, 459(1): 1104--1123

2016
[37]

Malerba, D. 1995. Page Blocks Classification Dataset . UCI Machine Learning Repository

1995
[38]

Mazumder, R.; Meng, X.; and Wang, H. 2022. Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features . In Proceedings of ICML-22, 15255--15277

2022
[39]

McTavish, H.; Zhong, C.; Achermann, R.; Karimalis, I.; Chen, J.; Rudin, C.; and Seltzer, M. 2022. Fast Sparse Decision Tree Optimization via Reference Ensembles . In Proceedings of AAAI-22, 9604--9613

2022
[40]

K.; and Salzberg, S

Murthy, S. K.; and Salzberg, S. 1995. Decision Tree Induction: How Effective Is the Greedy Heuristic? In Proceedings of KDD-95, 222--227

1995
[41]

Narodytska, N.; Ignatiev, A.; Pereira, F.; and Marques-Silva, J. 2018. Learning Optimal Decision Trees with SAT . In Proceedings of IJCAI-18, 1362--1368

2018
[42]

Nijssen, S.; and Fromont, E. 2007. Mining Optimal Decision Trees from Itemset Lattices . In Proceedings of SIGKDD-07, 530--539

2007
[43]

Nijssen, S.; and Fromont, E. 2010. Optimal constraint-based decision tree induction from itemset lattices . Data Mining and Knowledge Discovery, 21(1): 9--51

2010
[44]

Quinlan, J. R. 1993. C4.5: Programs for Machine Learning . San Francisco, CA: Morgan Kaufmann Publishers Inc

1993
[45]

Roesler, O. 2013. EEG Eye State Dataset . UCI Machine Learning Repository

2013
[46]

Rudin, C. 2019. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead . Nature Machine Intelligence, 1(5): 206--215

2019
[47]

Shati, P.; Cohen, E.; and McIlraith, S. 2021. SAT-Based Approach for Learning Optimal Decision Trees with Non-Binary Features . In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP-2021), 50:1--50:16

2021
[48]

Shati, P.; Cohen, E.; and McIlraith, S. A. 2023. SAT-based optimal classification trees for non-binary data . Constraints, 28(2): 166--202

2023
[49]

P.; Jain, V.; Chaudhari, S.; Kraemer, F

Singh, A. P.; Jain, V.; Chaudhari, S.; Kraemer, F. A.; Werner, S.; and Garg, V. 2018. Machine learning-based occupancy estimation using multivariate sensor nodes. In 2018 IEEE Globecom Workshops, 1--6

2018
[50]

Stefano, C.; Fontanella, F.; Maniaci, M.; and Freca, A. 2018. Avila Dataset . UCI Machine Learning Repository

2018
[51]

Van den Bos, M.; Van der Linden, J. G. M.; and Demirovi \' c , E. 2024. Piecewise Constant and Linear Regression Trees: An Optimal Dynamic Programming Approach . In Proceedings of ICML-24

2024
[52]

Van der Linden, J. G. M.; De Weerdt, M. M.; and Demirovi \' c , E. 2023. Necessary and Sufficient Conditions for Optimal Decision Trees using Dynamic Programming . In Advances in NeurIPS-23, 9173--9212

2023
[53]

Van der Linden, J. G. M.; Vos, D.; De Weerdt, M. M.; Verwer, S.; and Demirovi \' c , E. 2024. Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance . arXiv preprint arXiv:2409.12788

2024 arXiv
[54]

Verhaeghe, H.; Nijssen, S.; Pesant, G.; Quimper, C.-G.; and Schaus, P. 2020. Learning Optimal Decision Trees using Constraint Programming . Constraints, 25(3): 226--250

2020
[55]

Verwer, S.; and Zhang, Y. 2017. Learning decision trees with flexible constraints and objectives using integer optimization . In Proceedings of CPAIOR-17, 94--103

2017
[56]

Verwer, S.; and Zhang, Y. 2019. Learning Optimal Classification Trees Using a Binary Linear Program Formulation . In Proceedings of AAAI-19, 1625--1632

2019
[57]

Zhang, R.; Xin, R.; Seltzer, M.; and Rudin, C. 2023. Optimal Sparse Regression Trees . In Proceedings of AAAI-23, 11270--11279

2023

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [1]

, " * write output.state after.block = add.period write newline

ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...

[2] [2]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...

[3] [3]

Aghaei, S.; G \' o mez, A.; and Vayanos, P. 2024. Strong Optimal Classification Trees . Operations Research

work page 2024

[4] [4]

Aglin, G.; Nijssen, S.; and Schaus, P. 2020 a . Learning Optimal Decision Trees Using Caching Branch-and-Bound Search . In Proceedings of AAAI-20, 3146--3153

work page 2020

[5] [5]

Aglin, G.; Nijssen, S.; and Schaus, P. 2020 b . PyDL8.5: a Library for Learning Optimal Decision Trees . In Proceedings of IJCAI-20, 5222--5224

work page 2020

[6] [6]

Al \` e s, Z.; Hur \' e , V.; and Lambert, A. 2024. New optimization models for optimal classification trees . Computers & Operations Research , 164: 106515

work page 2024

[7] [7]

Al \` o s, J.; Ans \' o tegui, C.; and Torres, E. 2023. Interpretable decision trees through MaxSAT . Artificial Intelligence Review, 56(8): 8303--8323

work page 2023

[8] [8]

B.; D \' i az-Rodr \' i guez, N.; Del Ser, J.; Bennetot, A.; Tabik, S.; Barbado, A.; Garc \' i a, S.; Gil-L \' o pez, S.; Molina, D.; Benjamins, R.; Chatila, R.; and Herrera, F

Arrieta, A. B.; D \' i az-Rodr \' i guez, N.; Del Ser, J.; Bennetot, A.; Tabik, S.; Barbado, A.; Garc \' i a, S.; Gil-L \' o pez, S.; Molina, D.; Benjamins, R.; Chatila, R.; and Herrera, F. 2020. Explainable Artificial Intelligence (XAI): Concepts, taxonomies, opportunities and challenges toward responsible AI . Information Fusion, 58: 82--115

work page 2020