  


Interdiction of a MixedInteger Linear System
Bowen Hua(bhuautexas.edu) Abstract: A systeminterdiction problem can be modeled as a bilevel program in which the upper level models interdiction decisions and the lower level models system operation. This paper studies MILSIP, a mixedinteger linear system interdiction problem, which assumes binary interdiction decisions and models system operations through a mixedinteger linear program. To solve largescale instances of MILSIP, we apply Benders decomposition to a singlelevel reformulation of MILSIP. We identify ``significant'' linear programming subproblems whose feasibility implies the optimality of MILSIP. We propose an algorithm that that solves in each iteration: a relaxed master problem, a lowerlevel problem, and a significant subproblem. We demonstrate the algorithm's computational capabilities on a natural gas transmission system with 32 interdictable components. Numerical tests show that our algorithm solves certain problem instances an order of magnitude faster than an alternative algorithm from the literature. Keywords: interdiction, bilevel programming, decomposition Category 1: Integer Programming Category 2: Applications  OR and Management Sciences (Other ) Citation: Download: [PDF] Entry Submitted: 01/04/2019 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  