Solving the traveling salesman problem with interdiction and fortification

We solve a defender-attacker-defender problem over a traveling salesman problem (TSP), in which the defender first acts to defend a subset of arcs, the attacker then interdicts a subset of undefended arcs (thus increasing their costs), and the defender solves a TSP over the remaining network. Our approach employs an exact approach augmented with a TSP restriction phase to accelerate the convergence of the algorithm. Our computational results show success for the first time in optimally solving defender-attacker-defender TSP problems.