New Core-Guided and Hitting Set Algorithms for Multi-Objective Combinatorial Optimization
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Empirical Evaluation of the Implicit Hitting Set Approach for Weighted CSPs
SAT technology has proven to be surprisingly effective in a large variety of domains. However, for the Weighted CSP problem dedicated algorithms have always been superior. One approach not well-studied so far is the use …
Are Hitting Formulas Hard for Resolution?
Hitting formulas, introduced by Iwama, are an unusual class of propositional CNF formulas. Not only is their satisfiability decidable in polynomial time, but even their models can be counted in closed form. This stands i…
Optimal Algorithms for Range Searching over Multi-Armed Bandits
This paper studies a multi-armed bandit (MAB) version of the range-searching problem. In its basic form, range searching considers as input a set of points (on the real line) and a collection of (real) intervals. Here, w…
Multi-Armed BanditsDrift Analysis with Fitness Levels for Elitist Evolutionary Algorithms
The fitness level method is a popular tool for analyzing the hitting time of elitist evolutionary algorithms. Its idea is to divide the search space into multiple fitness levels and estimate lower and upper bounds on the…
Evolutionary AlgorithmsThe minimal hitting set generation problem: algorithms and computation
Finding inclusion-minimal "hitting sets" for a given collection of sets is a fundamental combinatorial problem with applications in domains as diverse as Boolean algebra, computational biology, and data mining. Much of t…
General Classification