Integer bilevel programming problems are known to be very challenging due to the lack of strong relaxations that can be efficiently computed. We propose single-level representations of integer bilevel programming problems that rely on network flow-based approximations of the follower's value function using decision diagrams. We then show how we can derive scalable relaxations from this representation by using relaxed decision diagrams, yielding dual bounds. We experimentally compare our approach with state-of-the-art bilevel programming solvers and show that we can obtain competitive results for certain problem classes.

We present a branch-and-cut method for solving convex integer nonlinear bilevel problems, i.e., bilevel models with nonlinear but convex objective functions and constraints in both the upper and the lower level. To this end, we generalize the idea of using disjunctive cuts to cut off integer-feasible but bilevel-infeasible points. These cuts can be obtained by solving a cut-generation problem, which itself is a single-level but nonconvex integer nonlinear problem. We show that this cut-generation problem can be decomposed into a series of smaller subproblems, that can all be solved in parallel and for which we can state assumptions under which all of them are convex integer nonlinear problems. Moreover, we develop additional algorithmic techniques such as tailored pruning rules to further speed up our method. We finally prove the correctness of the method and test it in a numerical study that shows the applicability of the method.

In the minimum spanning tree (MST) interdiction problem, the objective is to maximize the MST weight of a graph by deleting some edges. Each deleted edge incurs a cost, and there is a limit on the total expenditure. MST interdiction is known to be NP-complete even when all costs are 1 and weights are 0 or 1 (Fredrickson and Solis-Oba 1999). Since MSTs are minimum weight bases in the graphic matroid, this problem can be seen as a special case of the matroid interdiction problem, in which the objective is to maximize the minimum basis weight of a matroid by deleting some elements.

We develop a new branch-and-bound framework for solving matroid interdiction to optimality. For the case of MST interdiction, we show how to compute strong upper bounds by using dynamic programming over the solutions to minimum cut problems in related graphs. Furthermore, we show that a similar dynamic programming algorithm is able to exactly solve partition matroid interdiction, showing that partition matroid interdiction is only weakly NP-hard. For other matroids, we provide a set of tools that can be utilized to derive similar results.

Our algorithm achieves state-of-the-art computational performance for MST interdiction. In our preliminary computational tests, our algorithm was able to solve all instances from the literature in only a few minutes; many of these instances could not be solved within 3 hours by the previous best algorithms (Wei et al 2021). Our algorithm quickly solves typical instances with thousands of edges. We hope to apply our framework to more matroids and related problems in the future.

A combinatorial pricing problems (CPP) is a bilevel problem where we have a finite set of items, for which a leader sets the price of some of them (i.e. tolled items). Then, a follower observes the prices set by the leader and determines a subset of items to select by solving a combinatorial optimization problem. The latter must be expressed as a binary linear program. We take the perspective of the leader, whose objective is to set the prices of tolled items in order to maximize the revenue related to the items selected by the follower.
In this talk, we present a single-level reformulation of the CPP by rewriting the follower’s problem as a longest path problem using a dynamic programming model. In particular, we show the reformulation using the well-known decision diagrams and a novel dynamic programming model called the selection diagrams. Due to the single-level reformulations non-compact size, we provide a cutting-plan methodology for solving them. Finally, we validate our general-purpose framework by testing it on different CPPs.