Exploring Alternative Machine Learning Models for Variable Ordering in Cylindrical Algebraic Decomposition

Cylindrical Algebraic Decomposition is a computer algebra tool with many applications, from robotics to biochemistry. But it can be very sensitive to the ordering of the variables, which may be partially prescribed by the problem, but generally has at least some freedom. While various algorithmic heuristics to choose the best variable order exist, we are looking at using new machine learning models to pick the variable order directly. Of those machine learning methods we have currently implemented, Feed-forward networks seem the most successful (though some others are nearly as good), and much better than a traditional hand crafted heuristic such as Brown’s. We also explore an implementation of Graph Neural Networks as well as possible data pollution in current CAD datasets.