# Comparing machine learning models to choose the variable ordering for cylindrical algebraic decomposition

arXiv: https://arxiv.org/abs/1904.11061 · HTML: https://mlsanity.com/paper/1904.11061/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Apr 2019.

## Built on by (most cited first, 7 of 7)

- [Explainable AI Insights for Symbolic Computation: A case study on selecting the variable ordering for cylindrical algebraic decomposition](https://mlsanity.com/paper/2304.12154/) (2023)
- [Data Augmentation for Mathematical Objects](https://mlsanity.com/paper/2307.06984/) (2023)
- [Lessons on Datasets and Paradigms in Machine Learning for Symbolic Computation: A Case Study on CAD](https://mlsanity.com/paper/2401.13343/) (2024)
- [Revisiting Variable Ordering for Real Quantifier Elimination using Machine Learning](https://mlsanity.com/paper/2302.14038/) (2023)
- [Constrained Neural Networks for Interpretable Heuristic Creation to Optimise Computer Algebra Systems](https://mlsanity.com/paper/2404.17508/) (2024)
- [SC-Square: Future Progress with Machine Learning?](https://mlsanity.com/paper/2209.04361/) (2022)
- [Breaking the Data Barrier in Learning Symbolic Computation: A Case Study on Variable Ordering Suggestion for Cylindrical Algebraic Decomposition](https://mlsanity.com/paper/2601.13731/) (2026)

## Abstract (arXiv)

There has been recent interest in the use of machine learning (ML) approaches within mathematical software to make choices that impact on the computing performance without affecting the mathematical correctness of the result. We address the problem of selecting the variable ordering for cylindrical algebraic decomposition (CAD), an important algorithm in Symbolic Computation. Prior work to apply ML on this problem implemented a Support Vector Machine (SVM) to select between three existing human-made heuristics, which did better than anyone heuristic alone. The present work extends to have ML select the variable ordering directly, and to try a wider variety of ML techniques. We experimented with the NLSAT dataset and the Regular Chains Library CAD function for Maple 2018. For each problem, the variable ordering leading to the shortest computing time was selected as the target class for ML. Features were generated from the polynomial input and used to train the following ML models: k-nearest neighbours (KNN) classifier, multi-layer perceptron (MLP), decision tree (DT) and SVM, as implemented in the Python scikit-learn package. We also compared these with the two leading human constructed heuristics for the problem: Brown's heuristic and sotd. On this dataset all of the ML approaches outperformed the human made heuristics, some by a large margin.