# New Core-Guided and Hitting Set Algorithms for Multi-Objective Combinatorial Optimization

arXiv: https://arxiv.org/abs/2204.10856 · HTML: https://mlsanity.com/paper/2204.10856/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 27 references that are in the map.
- First posted on arXiv 22 Apr 2022.

## Builds on (most cited first, 2 of 2)

- [ARJA: Automated Repair of Java Programs via Multi-Objective Genetic Programming](https://mlsanity.com/paper/1712.07804/) (2017)
- [Generalized Totalizer Encoding for Pseudo-Boolean Constraints](https://mlsanity.com/paper/1507.05920/) (2015)

## Built on by (most cited first, 1 of 1)

- [Certifying Pareto-Optimality in Multi-Objective Maximum Satisfiability](https://mlsanity.com/paper/2501.17493/) (2025)

## Abstract (arXiv)

In the last decade, a plethora of algorithms for single-objective Boolean optimization has 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 still scarce. Due to this shortage of efficient tools for MOCO, many real-world applications formulated as multi-objective are simplified to single-objective, using either a linear combination or a lexicographic ordering of the objective functions to optimize. In this paper, we extend the state of the art of MOCO solvers with two novel unsatisfiability-based algorithms. The first is a core-guided MOCO solver. The second is a hitting set-based MOCO solver. Experimental results obtained in a wide range of benchmark instances show that our new unsatisfiability-based algorithms can outperform state-of-the-art SAT-based algorithms for MOCO.