Страница публикации

Branch location problems with maximum satisfiability

Тип публикации: Статья в журнале

Тип материала: Текст

Авторы: Zaikin O., Ignatiev A., Marques-Silva J.

Журнал: Frontiers in Artificial Intelligence and Applications

Язык публикации: english

Том: 325

Номера страниц: 379-386

Количество страниц: 8

Год публикации: 2020

Отчетный год: 2020

DOI: 10.3233/FAIA200116

Аннотация: Constrained location problems find a wide range of practical applications. Recent work showed that dedicated brute-force algorithms and greedy approach enable solutions of reasonable efficiency, for a restriction of the general constrained location problem, referred to as the branch location problem. This paper extends earlier work in several ways. First, the paper develops propositional encodings for the branch location problem. Second, given that the branch location problem is a restriction of the general constraint location problem, the paper shows that the restricted problem is still hard for NP. Third, the paper devises improved propositional encodings for the branch location problem, which in practice enable not only solving exactly a significantly larger class of problems but also effectively approximating optimal problem solutions, using state-of-the-art (complete and incomplete) Maximum Satisfiability (MaxSAT) solvers.

Индексируется WOS: Q5

Индексируется Scopus: Нет

Индексируется УБС: Нет

Индексируется РИНЦ: Да

Индексируется ВАК: Нет

Индексируется CORE: Нет