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

Şuvak Z., ALTINEL İ. K., ARAS M. N.

European Journal of Operational Research, cilt.287, sa.2, ss.410-437, 2020 (SCI-Expanded, Scopus) identifier identifier

  • 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.