An algorithm for the optimal solution of variable knockout problems

J. E. Beasley

Published 2019-08-06Version 1

In this paper we consider a class of problems related to variable knockout. Given an optimisation problem formulated as an integer program the question we face in problems of this type is what might be an appropriate set of variables to delete, i.e. knockout of the problem, in order that the optimal solution to the problem that remains after variable knockout has a desired property. We present an algorithm for the optimal solution of the problem. We indicate how our algorithm can be adapted when the number of variables knocked out is specified (i.e. when we have a cardinality constraint). Computational results are given for the problem of finding the minimal number of arcs to knockout from a directed network such that, after knockout, the shortest path from an origin node to a destination node is of length at least a specified value. We also present results for shortest path cardinality constrained knockout.