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

Branch location problems with maximum satisfiability

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

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

Том: 325

Номер:

Год: 2020

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

Издательство:

Местоположение издательства:

URL:

Аннотация: 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: 1

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

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

Публикация в печати: 0

Добавил в систему: