Optimization Online


Interdiction of a Mixed-Integer Linear System

Bowen Hua(bhua***at***utexas.edu)
Ross Baldick(baldick***at***ece.utexas.edu)
Kevin Wood(kwoodmry***at***gmail.com)

Abstract: A system-interdiction 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 mixed-integer linear system interdiction problem, which assumes binary interdiction decisions and models system operations through a mixed-integer linear program. To solve large-scale instances of MILSIP, we apply Benders decomposition to a single-level 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 lower-level 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 )


Download: [PDF]

Entry Submitted: 01/04/2019
Entry Accepted: 01/04/2019
Entry Last Modified: 01/04/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society