Rectilinear interdiction problem by locating a line barrier

Thesis Type: Postgraduate

Institution Of The Thesis: Middle East Technical University, Turkey

Approval Date: 2013

Thesis Language: English

Student: Hossein Gharehmeshk Gharravi

Supervisor: HALDUN SÜRAL


This study is an optimization approach to the rectilinear interdiction problem by locating a line barrier. Interdiction problems study the e ect of a limited disruption action on operations of a system. Network interdiction problems, where nodes and arcs of the network are susceptible to disruption actions, are extensively studied in the operations research literature. In this study, we consider a set of sink points on the plane that are being served by source points and our aim is to study the e ect of locating a line barrier on the plane (as a disruption action) such that the total shortest distance between sink and source points is maximized. We compute the shortest distances after disruption using visibility concept and utilizing properties of our problem. The amount of disruption is limited by imposing constraints on the length of the barrier and also the total number of disrupted points. The suggested solution approaches are based on mixed-integer programming and a polynomial-time algorithm.