Noah Weninger – Optimization Online

Interdiction of minimum spanning trees and other matroid bases

Published: 2024/07/24

0-1 Programming, Dynamic Programming, Graphs and Matroids bilevel optimization, Branch-and-Bound, dynamic programming, interdiction, knapsack problem, matroid, minimum spanning tree

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 … Read more

A Fast Combinatorial Algorithm for the Bilevel Knapsack Problem with Interdiction Constraints

Published: 2022/10/07

Noah Weninger

Ricardo Fukasawa

Combinatorial Optimization, Dynamic Programming bilevel optimization, Branch-and-Bound, dynamic programming, interdiction, knapsack problem

We consider the bilevel knapsack problem with interdiction constraints, a fundamental bilevel integer programming problem which generalizes the 0-1 knapsack problem. In this problem, there are two knapsacks and \(n\) items. The objective is to select some items to pack into the first knapsack such that the maximum profit attainable from packing some of the … Read more