将多种优化问题统一转化为MaxSAT求解,提升通用性。
A general optimization solver based on OP-to-MaxSAT reduction
- 通过自动归约将优化问题转为MaxSAT实例
- 在11类共136个问题上验证了求解效果
- 适合需要通用求解器的研究者和工程师
优化问题广泛存在于工程、经济和科学计算等领域。现有算法多针对特定类型,通用性有限。为此,我们提出一种自动化归约方法——OP-to-MaxSAT归约,并构建基于该归约的通用优化求解器GORED。GORED通过多项式时间将多种优化问题转化为MaxSAT实例,并利用先进的MaxSAT求解器进行求解。实验在11类共136个实例上验证了GORED的通用性与求解质量。结果表明,GORED能有效解决各类优化问题,且解的质量与现有方法无显著差异。该工作将优化求解范式从为每类问题设计专用算法,转变为使用单一算法处理多样化问题。未来该算法的进展可推动多个领域优化问题的整体进步。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。