Exact solution algorithms for the maximum flow problem with additional conflict constraints
European Journal of Operational Research, cilt.287, sa.2, ss.410-437, 2020 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 287 Sayı: 2
- Basım Tarihi: 2020
- Doi Numarası: 10.1016/j.ejor.2020.04.001
- Dergi Adı: European Journal of Operational Research
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, International Bibliography of Social Sciences, ABI/INFORM, Applied Science & Technology Source, Business Source Elite, Business Source Premier, Compendex, Computer & Applied Sciences, EconLit, INSPEC, Public Affairs Index, zbMATH, Civil Engineering Abstracts
- Sayfa Sayıları: ss.410-437
- Anahtar Kelimeler: Benders decomposition, branch-and-bound, Combinatorial optimization, Conflict, Maximum flow, Russian doll search
- Boğaziçi Üniversitesi Adresli: Evet
Özet
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.