Preprint · 2026 · Open access

An Exact Junction-Tree Extended Formulation for Optimal Classification Trees

Jiancheng Tu, WenqiFan

arXiv (Cornell University) · Published 21 September 2026 · DOI 10.48550/arxiv.2609.24741

Open PDFView at the publisherCite this paper

In brief

“An Exact Junction-Tree Extended Formulation for Optimal Classification Trees” is a 2026 preprint by Jiancheng Tu and WenqiFan, published in arXiv (Cornell University). OpenAlex counts 0 citations as of 21 November 2026. It is open access: the full text is free to read at arXiv (Cornell University).

Citations
0
References
30
Authors
2

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.

Cite this paper

Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.

APA 7

Tu, J., & WenqiFan. (2026). An Exact Junction-Tree Extended Formulation for Optimal Classification Trees. arXiv (Cornell University). https://doi.org/10.48550/arxiv.2609.24741

MLA 9

Tu, Jiancheng, and WenqiFan. “An Exact Junction-Tree Extended Formulation for Optimal Classification Trees.” arXiv (Cornell University), 2026. https://doi.org/10.48550/arxiv.2609.24741.

Chicago

Tu, Jiancheng and WenqiFan. 2026. “An Exact Junction-Tree Extended Formulation for Optimal Classification Trees.” arXiv (Cornell University). https://doi.org/10.48550/arxiv.2609.24741.

Harvard

Tu, J. and WenqiFan (2026) ‘An Exact Junction-Tree Extended Formulation for Optimal Classification Trees’, arXiv (Cornell University). doi:10.48550/arxiv.2609.24741.

IEEE

J. Tu and WenqiFan, “An Exact Junction-Tree Extended Formulation for Optimal Classification Trees,” arXiv (Cornell University), 2026, doi: 10.48550/arxiv.2609.24741.

BibTeX

@misc{tu2026exact,
  title     = {{An Exact Junction-Tree Extended Formulation for Optimal Classification Trees}},
  author    = {Tu, Jiancheng and WenqiFan},
  howpublished = {arXiv (Cornell University)},
  year      = {2026},
  doi       = {10.48550/arxiv.2609.24741},
  url       = {https://doi.org/10.48550/arxiv.2609.24741}
}

Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)

Topic and keywords

Physical Sciences › Computer Science › Information Systems › Data Mining Algorithms and Applications

  • linear programming formulation
  • binary features
  • column generation
  • message passing
  • exact reduction
  • mixed integer programming

Work with this paper

Most-cited papers in Computer Science

All highly cited Computer Science papers

Questions about this paper

How do I cite this paper in APA style?

Tu, J., & WenqiFan. (2026). An Exact Junction-Tree Extended Formulation for Optimal Classification Trees. arXiv (Cornell University). https://doi.org/10.48550/arxiv.2609.24741

How many times has this paper been cited?

0 times, according to OpenAlex on 21 November 2026. Google Scholar and Scopus count different sets of sources, so their numbers differ.

Is this paper free to read?

Yes. It is open access at arXiv (Cornell University): sign in and open the PDF from this page.

Who wrote this paper?

Jiancheng Tu, WenqiFan.

What is the DOI of this paper?

10.48550/arxiv.2609.24741, permanently at https://doi.org/10.48550/arxiv.2609.24741. Sign in and open it from this page.

Bibliographic data from OpenAlex (CC0), last checked 21 November 2026. ResearchGuru does not host this paper; once you are signed in, the links open it at the publisher or the repository that does.