Reproduce “Machine Learning for SAT: Restricted Heuristics and New Graph Representations” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Mikhail Shirokikh, Ilya Shenbin, Anton Alekseev, Sergey Nikolenko
Researchers enhanced SAT solver performance by integrating machine learning heuristics while mitigating their computational overhead through strategies like restricted usage and action pooling. They also developed a specialized graph representation for Open Shop Scheduling Problem instances, which made GNN-based SAT solving more efficient for these structured problems.
Key insights
- Integrating machine learning heuristics into SAT solvers requires careful management of computational overhead to outweigh their benefits.
- Combining the initial guidance from machine learning models with the later efficiency of classical heuristics leverages complementary strengths.
- Tailoring graph representations to the specific structure of the source problem (e.g., scheduling) can significantly enhance the efficiency and applicability of GNN-based SAT solvers.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.