  In the minimum spanning tree (MST) interdiction problem, we are given a graph
$G=(V,E)$ with edge weights, and want to find some $X\subseteq E$ satisfying a
knapsack constraint such that the MST weight in $(V,E\setminus X)$ is
maximized. Since MSTs of $G$ are the minimum weight bases in the graphic
matroid of $G$, this problem is a special case of matroid interdiction on a
matroid $M=(E,\mathcal{I})$, in which the objective is instead to maximize the
minimum weight of a basis of $M$ which is disjoint from $X$. By reduction from
0-1 knapsack, matroid interdiction is NP-complete, even for uniform matroids.
  We develop a new exact algorithm to solve the matroid interdiction problem.
One of the key components of our algorithm is a dynamic programming upper bound
which only requires that a simpler discrete derivative problem can be
calculated/approximated for the given matroid. Our exact algorithm then uses
this bound within a custom branch-and-bound algorithm. For different matroids,
we show how this discrete derivative can be calculated/approximated. In
particular, for partition matroids, this yields a pseudopolynomial time
algorithm. For graphic matroids, an approximation can be obtained by solving a
sequence of minimum cut problems, which we apply to the MST interdiction
problem. The running time of our algorithm is asymptotically faster than the
best known MST interdiction algorithm, up to polylog factors. Furthermore, our
algorithm achieves state-of-the-art computational performance: we solved all
available instances from the literature, and in many cases reduced the best
running time from hours to seconds.
