Exact solution algorithms for the maximum flow problem with additional conflict constraints

BaşlıkExact solution algorithms for the maximum flow problem with additional conflict constraints
Publication TypeJournal Article
Year of Publication2020
AuthorsŞuvak, Z., K. I. Altinel, and N. Aras
JournalEuropean Journal of Operational Research
Volume287
Pagination410-437
ISSN0377-2217
Anahtar kelimelerBenders decomposition, Branch-and-bound, Combinatorial optimization, Conflict, Maximum flow, Russian doll search
Abstract

We consider a variant of the maximum flow problem on a given directed graph where some arc pairs are incompatible or conflicting; in other words, they are not allowed to carry positive flow simultaneously. This problem, called the maximum flow problem with conflicts, is known to be strongly NP-hard. In this paper, we present mixed-integer linear programming formulations for the problem and develop exact solution methods based on Benders decomposition, branch-and-bound, and Russian Doll Search over the conflict graph which represents the conflict relations. The effectiveness of the proposed algorithms is tested on a large number of randomly generated instances. The results reveal that their performances are superior to solving the mixed-integer linear programming formulations with a commercial software.

URLhttps://www.sciencedirect.com/science/article/pii/S0377221720303192
DOI10.1016/j.ejor.2020.04.001