A Combinatorial Benders Decomposition Algorithm for the Directed Multiflow Network Diversion Problem

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 21
  • Download : 0
The network diversion problem is to identify a minimum cost, minimal cut separating a source node from a sink node that includes a predefined diversion arc and guarantees existence of a directed path between the source and sink nodes that includes no arc in the cut except for the diversion arc. We extend this to a problem having many source-sink pairs and call this extended problem the multiple flows network diversion problem. We propose optimization algorithms for the multiple flows network diversion problem using a combinatorial Benders decomposition approach incorporated into a branch-and-cut algorithm. We report computational results on four types of network topologies including two real-world networks that indicate that the proposed algorithms outperform state-of-the-art integer programming formulations.
Publisher
MILITARY OPERATIONS RESEARCH SOC
Issue Date
2019-09
Language
English
Article Type
Article
Citation

MILITARY OPERATIONS RESEARCH, v.24, no.1, pp.23 - 39

ISSN
1082-5983
DOI
10.5711/1082598324123
URI
http://hdl.handle.net/10203/267539
Appears in Collection
IE-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0