@article {1441, title = {Exact solution algorithms for the maximum flow problem with additional conflict constraints}, journal = {European Journal of Operational Research}, volume = {287}, year = {2020}, pages = {410-437}, 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.

}, keywords = {Benders decomposition, Branch-and-bound, Combinatorial optimization, Conflict, Maximum flow, Russian doll search}, issn = {0377-2217}, doi = {https://doi.org/10.1016/j.ejor.2020.04.001}, url = {https://www.sciencedirect.com/science/article/pii/S0377221720303192}, author = {Zeynep {\c S}uvak and I. Kuban Altinel and Necati Aras} }