A general optimization solver based on OP-to-MaxSAT reduction

Computer Science > Logic in Computer Science [Submitted on 23 Apr 2026] A general optimization solver based on OP-to-MaxSAT reduction Yuxin Zhao, Han Huang, Zhifeng Hao Optimization problems are fundamental in diverse fields, such as engineering, economics, and scientific computing. However, current algorithms are mostly designed for specific problem types and exhibit limited generality in solving multiple types of optimization problems. To enhance generality, we propose an automated reduction method named OP-to-MaxSAT reduction and a general optimization solver based on OP-to-MaxSAT reduction (GORED). GORED unifies the solving of multiple types of optimization problems by reducing the problems from optimization problems to MaxSAT instances in polynomial time and solving them using the state-of-the-art MaxSAT solver. The generality and solution quality of GORED are validated through experiments on 136 instances across 11 types of optimization problems. Experimental results demonstrate that GORED not only successfully solves a wide range of optimization problems but also yields solutions comparable in quality to those from existing methods, with no statistically significant differences observed. By introducing automated reduction, this work shifts the paradigm of optimization solvers from designing specialized algorithms for each problem type to employing a single algorithm for diverse problems. As a result, advances in this single algorithm can now drive progress in a wide range of optimization problems across various domains. Subjects: Logic in Computer Science (cs.LO); Artificial Intelligence (cs.AI); Symbolic Computation (cs.SC) Cite as: arXiv:2604.21961 [cs.LO]   (or arXiv:2604.21961v1 [cs.LO] for this version)   https://doi.org/10.48550/arXiv.2604.21961 Focus to learn more Submission history From: Yuxin Zhao [view email] [v1] Thu, 23 Apr 2026 16:03:12 UTC (161 KB) Access Paper: HTML (experimental) view license Current browse context: cs.LO < prev   |   next > new | recent | 2026-04 Change to browse by: cs cs.AI cs.SC References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)