A Lagrangian Heuristic for solving a network interdiction problem
| dc.contributor.advisor | Wood, R. Kevin | |
| dc.contributor.author | Bingol, Levent | |
| dc.contributor.department | Operations Research (OR) | |
| dc.date.accessioned | 2012-03-14T17:31:36Z | |
| dc.date.available | 2012-03-14T17:31:36Z | |
| dc.date.issued | 2001-12 | |
| dc.description.abstract | This thesis is concerned with solving or approximately solving a maximum-flow network-interdiction problem denoted MXFI: A network user strives to maximize flow of a commodity through a capacitated network, while an interdictor, with limited assets, attempts to destroy links in the network to minimize that maximum flow. MXFI can be converted to a binary integer program and solved but this approach can be computationally expensive. Earlier work by Derbes (1997) on a Lagrangian-relaxation technique has shown promise for solving the problem more quickly (Derbes, 1997). We extend his technique and implement algorithms in C to solve MXFI for all integer values of total interdiction resource available, R, in some specified range; interdictable arcs require one unit of resource to destroy. The basic procedure solves MXFI exactly for most values of R, but βproblematic valuesγ of R do arise. For one set of test problems, a heuristic handles these values successfully, with optimality gaps that are typically less than three percent. We test our algorithms and implementations using five test networks which range in size from 27 nodes and 86 arcs to 402 nodes and 1826 arcs. Using a 700 MHz Pentium III personal computer, we solve the largest problem in 16 seconds. | en_US |
| dc.description.service | Turkish Navy author | en_US |
| dc.description.uri | http://archive.org/details/alagrangiheurist109451385 | |
| dc.format.extent | xvii, 37 p. ; | en_US |
| dc.identifier.oclc | 266044 | |
| dc.identifier.uri | https://hdl.handle.net/10945/1385 | |
| dc.publisher | Monterey, California. Naval Postgraduate School | en_US |
| dc.rights | This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States. | en_US |
| dc.title | A Lagrangian Heuristic for solving a network interdiction problem | en_US |
| dc.type | Thesis | en_US |
| dspace.entity.type | Publication | |
| etd.thesisdegree.discipline | Operations Research | en_US |
| etd.thesisdegree.grantor | Naval Postgraduate School | en_US |
| etd.thesisdegree.level | Masters | en_US |
| etd.thesisdegree.name | M.S. | en_US |
| etd.verified | no | en_US |
Files
Original bundle
1 - 1 of 1