Cutting plane approach for the maximum flow interdiction problem View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2017-12

AUTHORS

Joe Naoum-Sawaya, Bissan Ghaddar

ABSTRACT

The maximum flow interdiction is a class of leader–follower optimization problems that seek to identify the set of edges in a network whose interruption minimizes the maximum flow across the network. Particularly, maximum flow interdiction is important in assessing the vulnerability of networks to disruptions. In this paper, the problem is formulated as a bi-level mixed-integer program and an iterative cutting plane algorithm is proposed as a solution methodology. The cutting planes are implemented in a branch-and-cut approach that is computationally effective. Extensive computational results are presented on 336 different instances with varying parameters and with networks of sizes up to 50 nodes, 1200 edge, and 800 commodities. The computational results show that the proposed cutting plane approach has significant computational advantage over the direct solution of the monolithic formulation of the maximum flow interdiction problem for the majority of the tested instances. More... »

PAGES

1553-1569

Identifiers

URI

http://scigraph.springernature.com/pub.10.1057/s41274-017-0185-8

DOI

http://dx.doi.org/10.1057/s41274-017-0185-8

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1083877196


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Western University", 
          "id": "https://www.grid.ac/institutes/grid.39381.30", 
          "name": [
            "Ivey Business School, Western University, 1255 Western Road, N6G 0N1, London, ON, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Naoum-Sawaya", 
        "givenName": "Joe", 
        "id": "sg:person.0614106446.44", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0614106446.44"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Waterloo", 
          "id": "https://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "Department of Management Sciences, University of Waterloo, 200 University Avenue W., N2L 3G1, Waterloo, ON, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ghaddar", 
        "givenName": "Bissan", 
        "id": "sg:person.012422453071.64", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012422453071.64"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/s0377-2217(03)00135-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002300802"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0377-2217(03)00135-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002300802"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.dam.2015.05.036", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014492745"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.dam.2015.05.036", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014492745"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.dam.2015.05.036", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014492745"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.dam.2015.05.036", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014492745"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.cor.2007.09.004", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017248123"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.dam.2010.04.008", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019287346"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10107-013-0642-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019962453", 
          "https://doi.org/10.1007/s10107-013-0642-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.orl.2014.07.010", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027829311"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-57762-8_13", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031577503", 
          "https://doi.org/10.1007/978-3-642-57762-8_13"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-57762-8_13", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031577503", 
          "https://doi.org/10.1007/978-3-642-57762-8_13"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0377-2217(01)00275-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034250746"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.disopt.2012.07.001", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039887523"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.cor.2006.09.019", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043524474"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0377-2217(96)00085-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048883893"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0166-218x(00)00310-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050476612"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.cor.2012.08.013", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052342767"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0895-7177(93)90236-r", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052637154"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/ijoc.2015.0671", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064707297"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/inte.30.1.26.11621", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064710264"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/mnsc.15.9.506", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064716534"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/mnsc.20.5.822", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064717374"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.1975.21", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086241959"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2017-12", 
    "datePublishedReg": "2017-12-01", 
    "description": "The maximum flow interdiction is a class of leader\u2013follower optimization problems that seek to identify the set of edges in a network whose interruption minimizes the maximum flow across the network. Particularly, maximum flow interdiction is important in assessing the vulnerability of networks to disruptions. In this paper, the problem is formulated as a bi-level mixed-integer program and an iterative cutting plane algorithm is proposed as a solution methodology. The cutting planes are implemented in a branch-and-cut approach that is computationally effective. Extensive computational results are presented on 336 different instances with varying parameters and with networks of sizes up to 50 nodes, 1200 edge, and 800 commodities. The computational results show that the proposed cutting plane approach has significant computational advantage over the direct solution of the monolithic formulation of the maximum flow interdiction problem for the majority of the tested instances.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1057/s41274-017-0185-8", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1087747", 
        "issn": [
          "0160-5682", 
          "1476-9360"
        ], 
        "name": "Journal of the Operational Research Society", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "12", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "68"
      }
    ], 
    "name": "Cutting plane approach for the maximum flow interdiction problem", 
    "pagination": "1553-1569", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "3ce12b8d01994ad97145cb9995aab63cc03eb7410f5d7baecfb30680763fb552"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1057/s41274-017-0185-8"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1083877196"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1057/s41274-017-0185-8", 
      "https://app.dimensions.ai/details/publication/pub.1083877196"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T17:30", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8672_00000508.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1057/s41274-017-0185-8"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1057/s41274-017-0185-8'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1057/s41274-017-0185-8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1057/s41274-017-0185-8'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1057/s41274-017-0185-8'


 

This table displays all metadata directly associated to this object as RDF triples.

130 TRIPLES      21 PREDICATES      46 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1057/s41274-017-0185-8 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Ned4e262830424207b49d53bf2dcbd450
4 schema:citation sg:pub.10.1007/978-3-642-57762-8_13
5 sg:pub.10.1007/s10107-013-0642-3
6 https://doi.org/10.1016/0895-7177(93)90236-r
7 https://doi.org/10.1016/j.cor.2006.09.019
8 https://doi.org/10.1016/j.cor.2007.09.004
9 https://doi.org/10.1016/j.cor.2012.08.013
10 https://doi.org/10.1016/j.dam.2010.04.008
11 https://doi.org/10.1016/j.dam.2015.05.036
12 https://doi.org/10.1016/j.disopt.2012.07.001
13 https://doi.org/10.1016/j.orl.2014.07.010
14 https://doi.org/10.1016/s0166-218x(00)00310-3
15 https://doi.org/10.1016/s0377-2217(01)00275-2
16 https://doi.org/10.1016/s0377-2217(03)00135-8
17 https://doi.org/10.1016/s0377-2217(96)00085-9
18 https://doi.org/10.1109/sfcs.1975.21
19 https://doi.org/10.1287/ijoc.2015.0671
20 https://doi.org/10.1287/inte.30.1.26.11621
21 https://doi.org/10.1287/mnsc.15.9.506
22 https://doi.org/10.1287/mnsc.20.5.822
23 schema:datePublished 2017-12
24 schema:datePublishedReg 2017-12-01
25 schema:description The maximum flow interdiction is a class of leader–follower optimization problems that seek to identify the set of edges in a network whose interruption minimizes the maximum flow across the network. Particularly, maximum flow interdiction is important in assessing the vulnerability of networks to disruptions. In this paper, the problem is formulated as a bi-level mixed-integer program and an iterative cutting plane algorithm is proposed as a solution methodology. The cutting planes are implemented in a branch-and-cut approach that is computationally effective. Extensive computational results are presented on 336 different instances with varying parameters and with networks of sizes up to 50 nodes, 1200 edge, and 800 commodities. The computational results show that the proposed cutting plane approach has significant computational advantage over the direct solution of the monolithic formulation of the maximum flow interdiction problem for the majority of the tested instances.
26 schema:genre research_article
27 schema:inLanguage en
28 schema:isAccessibleForFree false
29 schema:isPartOf N025663eecd9d4db283023bfee3445d6f
30 N133171484292405d89d75fad0057896b
31 sg:journal.1087747
32 schema:name Cutting plane approach for the maximum flow interdiction problem
33 schema:pagination 1553-1569
34 schema:productId N088b409cc7c8478eb45ac1155c444dc5
35 N35c207fe87ef4bc68ece75576da28a2a
36 N8ed17dd31ab74a5f8d4b62e5b55e0bbb
37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1083877196
38 https://doi.org/10.1057/s41274-017-0185-8
39 schema:sdDatePublished 2019-04-10T17:30
40 schema:sdLicense https://scigraph.springernature.com/explorer/license/
41 schema:sdPublisher Nbfddb5cc24274b2dae8da1a7124032c8
42 schema:url http://link.springer.com/10.1057/s41274-017-0185-8
43 sgo:license sg:explorer/license/
44 sgo:sdDataset articles
45 rdf:type schema:ScholarlyArticle
46 N025663eecd9d4db283023bfee3445d6f schema:volumeNumber 68
47 rdf:type schema:PublicationVolume
48 N088b409cc7c8478eb45ac1155c444dc5 schema:name readcube_id
49 schema:value 3ce12b8d01994ad97145cb9995aab63cc03eb7410f5d7baecfb30680763fb552
50 rdf:type schema:PropertyValue
51 N133171484292405d89d75fad0057896b schema:issueNumber 12
52 rdf:type schema:PublicationIssue
53 N35c207fe87ef4bc68ece75576da28a2a schema:name doi
54 schema:value 10.1057/s41274-017-0185-8
55 rdf:type schema:PropertyValue
56 N47a8eb54787745a7a838a41c1d5e95bd rdf:first sg:person.012422453071.64
57 rdf:rest rdf:nil
58 N8ed17dd31ab74a5f8d4b62e5b55e0bbb schema:name dimensions_id
59 schema:value pub.1083877196
60 rdf:type schema:PropertyValue
61 Nbfddb5cc24274b2dae8da1a7124032c8 schema:name Springer Nature - SN SciGraph project
62 rdf:type schema:Organization
63 Ned4e262830424207b49d53bf2dcbd450 rdf:first sg:person.0614106446.44
64 rdf:rest N47a8eb54787745a7a838a41c1d5e95bd
65 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
66 schema:name Information and Computing Sciences
67 rdf:type schema:DefinedTerm
68 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
69 schema:name Computation Theory and Mathematics
70 rdf:type schema:DefinedTerm
71 sg:journal.1087747 schema:issn 0160-5682
72 1476-9360
73 schema:name Journal of the Operational Research Society
74 rdf:type schema:Periodical
75 sg:person.012422453071.64 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
76 schema:familyName Ghaddar
77 schema:givenName Bissan
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012422453071.64
79 rdf:type schema:Person
80 sg:person.0614106446.44 schema:affiliation https://www.grid.ac/institutes/grid.39381.30
81 schema:familyName Naoum-Sawaya
82 schema:givenName Joe
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0614106446.44
84 rdf:type schema:Person
85 sg:pub.10.1007/978-3-642-57762-8_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031577503
86 https://doi.org/10.1007/978-3-642-57762-8_13
87 rdf:type schema:CreativeWork
88 sg:pub.10.1007/s10107-013-0642-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019962453
89 https://doi.org/10.1007/s10107-013-0642-3
90 rdf:type schema:CreativeWork
91 https://doi.org/10.1016/0895-7177(93)90236-r schema:sameAs https://app.dimensions.ai/details/publication/pub.1052637154
92 rdf:type schema:CreativeWork
93 https://doi.org/10.1016/j.cor.2006.09.019 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043524474
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1016/j.cor.2007.09.004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017248123
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1016/j.cor.2012.08.013 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052342767
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1016/j.dam.2010.04.008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019287346
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1016/j.dam.2015.05.036 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014492745
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1016/j.disopt.2012.07.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039887523
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1016/j.orl.2014.07.010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027829311
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1016/s0166-218x(00)00310-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050476612
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1016/s0377-2217(01)00275-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034250746
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1016/s0377-2217(03)00135-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002300802
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1016/s0377-2217(96)00085-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048883893
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1109/sfcs.1975.21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086241959
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1287/ijoc.2015.0671 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064707297
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1287/inte.30.1.26.11621 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064710264
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1287/mnsc.15.9.506 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064716534
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1287/mnsc.20.5.822 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064717374
124 rdf:type schema:CreativeWork
125 https://www.grid.ac/institutes/grid.39381.30 schema:alternateName Western University
126 schema:name Ivey Business School, Western University, 1255 Western Road, N6G 0N1, London, ON, Canada
127 rdf:type schema:Organization
128 https://www.grid.ac/institutes/grid.46078.3d schema:alternateName University of Waterloo
129 schema:name Department of Management Sciences, University of Waterloo, 200 University Avenue W., N2L 3G1, Waterloo, ON, Canada
130 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...