Optimizing Optimizations: Case Study on Detecting Specific Types of Mathematical Optimization Constraints with E-Graphs in JijModeling
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.
Slides (Optimizing Optimizations.pdf) | 1.89MiB |
Tue 17 JunDisplayed time zone: Seoul change
09:00 - 10:10 | |||
09:00 20mTalk | Cut Tracing with E-Graphs for Boolean FHE Circuit SynthesisRecorded EGRAPHS Pre-print Media Attached | ||
09:20 20mTalk | Optimizing Optimizations: Case Study on Detecting Specific Types of Mathematical Optimization Constraints with E-Graphs in JijModeling EGRAPHS Media Attached File Attached | ||
09:40 20mTalk | Using Equality Saturation and Stochastic Mutations for Molecular Dynamics Code Optimization EGRAPHS Oren Hecht Technion, Yotam M. Y. Feldman Tel Aviv University, Barak Hirshberg Tel Aviv University, Hila Peleg Technion Media Attached |