Engineering and Evaluating Multi-objective Pseudo-Boolean Optimizers

doi:10.1007/978-3-032-04587-4_8

2026-01-01

PRE

Christoph Jabs *

Jeremias Berg

Matti Järvisalo

DOI：10.1007/978-3-032-04587-4_8

原文链接

原文求助

摘要

En 中文

现实世界的各种场景催生了具有多个冲突目标的组合优化问题，这促使人们开发解决多目标问题声明性模型中帕累托最优解的实用方法。本研究聚焦于伪布尔约束的多目标优化（MO-PBO），将其视为命题子句的扩展，同时也是一类重要的0-1线性约束。我们首次对适用于MO-PBO的几种近期提出的方法进行了跨领域评估，包括我们提供的原生MO-PBO算法的首个实现、基于整数线性规划技术的方法以及基于翻译的MO-MaxSAT方法，为当前MO-PBO领域的先进方法提供了见解。在算法进展方面，我们通过利用伪布尔约束决策程序的最新进展来构建MO-PBO求解器，以将近期为命题约束下的多目标优化（即MO-MaxSAT）开发的多元目标方法提升至MO-PBO领域。基于近期关于认证MO-MaxSAT求解的研究，我们还通过为我们的原生MO-PBO方法和基于翻译的MO-MaxSAT方法实现证明日志，实现了认证的多目标伪布尔优化。

Keyword:

Multi-objective optimization

pseudo-Boolean optimization

empirical evaluation

certified optimization