A general optimization solver based on OP-to-MaxSAT reduction
This work provides a unified approach to solving diverse optimization problems, potentially reducing the need for specialized algorithms for each problem type.
The paper proposes a general optimization solver, GORED, that reduces multiple types of optimization problems to MaxSAT instances in polynomial time and solves them using a state-of-the-art MaxSAT solver. Experiments on 136 instances across 11 problem types show that GORED achieves solution quality comparable to existing specialized methods with no statistically significant differences.
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.