Seminar on May 4, 2015



A Backward Sampling Framework for Interdiction Problems with Fortification


Cole Smith,

(Department of Industrial Engineering, Clemson University) 



This talk examines a class of three-stage sequential defender-attacker-defender problems. In these problems the defender first selects a subset of assets to protect, the attacker next damages a subset of unprotected assets in the "interdiction" stage, after which the defender optimizes a "recourse" problem over the surviving assets. These problems are notoriously difficult to optimize, and almost always require the recourse problem to be a convex optimization problem. Our contribution is a new approach to solving defender-attacker-defender problems. We require all variables in the first two stages to be binary-valued, but allow the recourse problem to take any form. The proposed framework focuses on solving the interdiction problem by restricting the defender to select a recourse decision from a sample of feasible vectors. The algorithm then iteratively refines the sample to force finite convergence to an optimal solution. This talk shows that our algorithm not only solves interdiction problems involving NP-hard recourse problems within reasonable computational limits, but it also solves shortest path fortification and interdiction problems more efficiently than state-of-the-art algorithms tailored for that problem, finding optimal solutions to real-road networks having up to 300,000 nodes and over 1,000,000 arcs.


Short Bio: 

Dr. J. Cole Smith is Professor and Chair of the Industrial Engineering department at Clemson University, a top-20 public research university in South Carolina, USA. He served as a tenured faculty member in the Industrial and Systems Engineering department at the University of Florida (UF) from 2005-2014, serving as Interim Department Chair in the 2013-2014 year. While at UF, he also served as the founding Interim Director of the UF Informatics Institute, a university-wide initiative that oversaw interdisciplinary endeavors in hiring and joint internal funding opportunities. His awards include the Young Investigator Award from the ONR, the Hamid K. Elden Outstanding Young Industrial Engineer in Education award, the Operations Research Division Teaching Award, and the best paper award from IIE Transactions in 2007. His Ph.D. graduates are currently employed in various industrial and governmental organizations worldwide, along with tenure/tenure-track academic positions at Arizona State, Arkansas, Bogazici, Michigan, and Wichita State.


All interested are cordially invited.  


DATE:  May 4, 2015 

TIME:  Monday, 15:00-16:00