Optimizing Optimizations: Case Study on Detecting Specific Types of Mathematical Optimization Constraints with E-Graphs in JijModeling

Abstract

In solving mathematical optimization problems efficiently, it is crucial to make use of information about specific types of constraints, such as the one-hot or Special-Ordered Set (SOS) constraints. In many cases, exploiting such information gives asymptotically better execution time. JijModeling, an industrial-strength mathematical optimization modeller, achieves this by separating the symbolic representation of an optimization problem from the input data.

In this paper, we will report a real-world case study on a constraint detection mechanism modulo the algebraic congruence using e-graphs, and describe heuristic criteria for designing rewriting systems. We give benchmarking result that shows the performance impact of the constraint detection mechanism. We also introduce egg_recursive, a utility library for writing egg-terms as recursive abstract syntax trees, reducing the burden of writing and maintaining complex terms in S-expressions.