Exact solution algorithms for the maximum flow problem with additional conflict constraints
|Title||Exact solution algorithms for the maximum flow problem with additional conflict constraints|
|Publication Type||Journal Article|
|Year of Publication||2020|
|Authors||Şuvak, Z., K. I. Altinel, and N. Aras|
|Journal||European Journal of Operational Research|
|Keywords||Benders decomposition, Branch-and-bound, Combinatorial optimization, Conflict, Maximum flow, Russian doll search|
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.