Branch location problems with maximum satisfiability

Oleg Zaikin, Alexey Ignatiev, Joao Marques-Silva

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

1 Citation (Scopus)


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.

Original languageEnglish
Title of host publicationECAI Digital - 2020
Subtitle of host publication24th European Conference on Artificial Intelligence
EditorsGiuseppe De Giacomo, Alejandro Catala, Bistra Dilkina, Michela Milano, Senen Barro, Alberto Bugarin, Jerome Lang
Place of PublicationAmsterdam Netherlands
PublisherIOS Press
Number of pages8
ISBN (Electronic)9781643681016
ISBN (Print)9781643681009
Publication statusPublished - 2020
EventEuropean Conference on Artificial Intelligence 2020 - Virtual, Santiago de Compostela, Spain
Duration: 29 Aug 20208 Sep 2020
Conference number: 24th (Website) (Proceedings)

Publication series

NameFrontiers in Artificial Intelligence and Applications
PublisherIOS Press
ISSN (Electronic)0922-6389


ConferenceEuropean Conference on Artificial Intelligence 2020
Abbreviated titleECAI 2020
CitySantiago de Compostela
Other24th European Conference on Artificial Intelligence, ECAI 2020, including 10th Conference on Prestigious Applications of Artificial Intelligence, PAIS 2020
Internet address

Cite this