Unsatisfiability-based Algorithms for Multi-Objective Combinatorial Optimization

doi:10.1007/s10817-026-09749-w

Return

Unsatisfiability-based Algorithms for Multi-Objective Combinatorial Optimization

2026-02-16

Cortes, Joao *

Inês Lynce

Vasco Manquinho

DOI：10.1007/s10817-026-09749-w

Original

Save

View PDF

Abstract

En 中文

In the last decade, numerous algorithms for single-objective Boolean optimization have been proposed that rely on the iterative usage of a highly effective Propositional Satisfiability (SAT) solver. But the use of SAT solvers in Multi-Objective Combinatorial Optimization (MOCO) algorithms is scarce. Due to the shortage of efficient tools for MOCO, many real-world applications formulated as multi-objective are cast as single-objective, using either a linear combination or by setting a preference order among the objectives. In this paper, we extend the state of the art of MOCO solvers with three novel unsatisfiability-based algorithms. The first two are core-guided MOCO solvers. The third is a hitting set MOCO solver. Experimental results in several sets of benchmark instances show that our new unsatisfiability-based algorithms can outperform and complement other SAT-based, state-of-the-art algorithms for MOCO.

Keywords:

Multi-objective combinatorial optimization

Unsatisfiability algorithms

Hitting sets

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.