Martin Schmidt Explainable artificial intelligence is one of the most important trends in modern machine-learning research. The idea is to explain the outcome of a model by presenting a certain change in the input of the model so that the outcome changes significantly. In this paper, we study this question for linear optimization problems as an automated … Read more
We study bilevel problems with a convex quadratic mixed-integer upper-level and a nonconvex quadratic, purely continuous lower-level problem. We prove $\Sigma_p^2$-hardness of this class of problems, derive an iterative lower- and upper-bounding scheme, and show its finiteness and correctness in the sense that it computes globally optimal points or proves infeasibility of the instance. To … Read more
We consider the household assignment problem as it occurs in the geo-referencing step of spatial microsimulation models. The resulting model is a maximum weight matching problem with additional side constraints. For real-world instances such as the one for the city of Trier in Germany, the number of binary variables exceeds 10^9, and the resulting instances … Read more
In this report, we present the BOBILib, a collection of more than 2500~instances of mixed integer linear bilevel optimization problems. The goal of this library is to make a large and well-curated set of test instances freely available for the research community so that new and existing algorithms in bilevel optimization can be tested and … Read more
In the context of mixed-integer nonlinear problems (MINLPs), it is well-known that strong duality does not hold in general if the standard Lagrangian dual is used. Hence, we consider the augmented Lagrangian dual (ALD), which adds a nonlinear penalty function to the classic Lagrangian function. For this setup, we study conditions under which the ALD … Read more
We consider the problem of determining optimal tolls in a traffic network in which a toll-setting authority aims to maximize revenues and the users of the network act in the sense of Wardrop’s user equilibrium. The setting is modeled as a mathematical problem with equilibrium constraints and a mixed-integer, nonlinear, and nonconvex reformulation is presented … Read more
We present a feedback scheme for non-cooperative dynamic games and investigate its stabilizing properties. The dynamic games are modeled as generalized Nash equilibrium problems (GNEP), in which the shared constraint consists of linear time-discrete dynamic equations (e.g., sampled from a partial or ordinary differential equation), which are jointly controlled by the players’ actions. Further, the … Read more
Random forests are among the most famous algorithms for solving classification problems, in particular for large-scale data sets. Considering a set of labeled points and several decision trees, the method takes the majority vote to classify a new given point. In some scenarios, however, labels are only accessible for a proper subset of the given … Read more
Due to their nested structure, bilevel problems are intrinsically hard to solve–even if all variables are continuous and all parameters of the problem are exactly known. In this paper, we study mixed-integer linear bilevel problems with lower-level objective uncertainty, which we address using the notion of Γ-robustness. To tackle the Γ-robust counterpart of the bilevel … Read more
We study network design problems for nonlinear and nonconvex flow models under demand uncertainties. To this end, we apply the concept of adjustable robust optimization to compute a network design that admits a feasible transport for all, possibly infinitely many, demand scenarios within a given uncertainty set. For solving the corresponding adjustable robust mixed-integer nonlinear … Read more