@unpublished{GrossGuptaKumaretal., author = {Groß, Martin and Gupta, Anupam and Kumar, Amit and Matuschke, Jannik and Schmidt, Daniel R. and Schmidt, Melanie and Verschae, Jos{\´e}}, title = {A Local-Search Algorithm for Steiner Forest}, abstract = {In the Steiner Forest problem, we are given a graph and a collection of source-sink pairs, and the goal is to find a subgraph of minimum total length such that all pairs are connected. The problem is APX-Hard and can be 2 -approximated by, e.g., the elegant primal-dual algorithm of Agrawal, Klein, and Ravi from 1995. We give a local-search-based constant-factor approximati on for the problem. Local search brings in new techniques to an area that has for long not seen any improv ements and might be a step towards a combinatorial algorithm for the more general survivable n etwork design problem. Moreover, local search was an essential tool to tackle the dynamic MST/Stein er Tree problem, whereas dynamic Steiner Forest is still wide open. It is easy to see that any constant factor local search algori thm requires steps that add/drop many edges together. We propose natural local moves which, at each step , either (a) add a shortest path in the current graph and then drop a bunch of inessential edges, or (b) add a s et of edges to the current solution. This second type of moves is motivated by the potential function w e use to measure progress, combining the cost of the solution with a penalty for each connected compon ent. Our carefully-chosen local moves and potential function work in tandem to eliminate bad local min ima that arise when using more traditional local moves. Our analysis first considers the case where the local optimum is a single tree, and shows optimality w.r.t. moves that add a single edge (and drop a set of edges) is enough to bound the locality gap. For the general case, we show how to "project" the optimal solution o nto the different trees of the local optimum without incurring too much cost (and this argument uses opti mality w.r.t. both kinds of moves), followed by a tree-by-tree argument. We hope both the potential funct ion, and our analysis techniques will be useful to develop and analyze local-search algorithms in ot her contexts.}, language = {en} } @unpublished{GrimmNowakScheweetal.2020, author = {Grimm, Veronika and Nowak, Daniel and Schewe, Lars and Schmidt, Martin and Schwartz, Alexandra and Z{\"o}ttl, Gregor}, title = {A Tractable Multi-Leader Multi-Follower Peak-Load-Pricing Model with Strategic Interaction}, doi = {10.1007/s10107-021-01708-0}, pages = {35}, year = {2020}, abstract = {While single-level Nash equilibrium problems are quite well understood nowadays, less is known about multi-leader multi-follower games. However, these have important applications, e.g., in the analysis of electricity and gas markets, where often a limited number of firms interacts on various subsequent markets. In this paper, we consider a special class of two-level multi-leader multi-follower games that can be applied, e.g., to model strategic booking decisions in the European entry-exit gas market. For this nontrivial class of games, we develop a solution algorithm that is able to compute the complete set of Nash equilibria instead of just individual solutions or a bigger set of stationary points. Additionally, we prove that for this class of games, the solution set is finite and provide examples for instances without any Nash equilibria in pure strategies. We apply the algorithm to a case study in which we compute strategic booking and nomination decisions in a model of the European entry-exit gas market system. Finally, we use our algorithm to provide a publicly available test library for the considered class of multi-leader multi-follower games. This library contains problem instances with different economic and mathematical properties so that other researchers in the field can test and benchmark newly developed methods for this challenging class of problems.}, language = {en} } @article{CacchianiJuengerLiersetal.2016, author = {Cacchiani, Valentina and J{\"u}nger, Michael and Liers, Frauke and Lodi, Andrea and Schmidt, Daniel}, title = {Single-commodity robust network design with finite and Hose demand sets}, series = {Mathematical Programming}, volume = {157}, journal = {Mathematical Programming}, number = {1}, doi = {10.1007/s10107-016-0991-9}, pages = {297 -- 342}, year = {2016}, abstract = {We study a single-commodity robust network design problem (sRND) defined on an undirected graph. Our goal is to determine minimum cost capacities such that any traffic demand from a given uncertainty set can be satisfied by a feasible single-commodity flow. We consider two ways of representing the uncertainty set, either as a finite list of scenarios or as a polytope. We propose a branch-and-cut algorithm to derive optimal solutions to sRND, built on a capacity-based integer linear programming formulation. It is strengthened with valid inequalities derived as {0, 1/2}-Chv{\´a}tal-Gomory cuts. Since the formulation contains exponentially many constraints, we provide practical separation algorithms. Extensive computational experiments show that our approach is effective, in comparison to existing approaches from the literature as well as to solving a flow based formulation by a general purpose solver.}, language = {en} } @unpublished{BeckSchmidtThueraufetal.2022, author = {Beck, Yasmine and Schmidt, Martin and Th{\"u}rauf, Johannes and Bienstock, Daniel}, title = {On a Computationally Ill-Behaved Bilevel Problem with a Continuous and Nonconvex Lower Level}, pages = {16}, year = {2022}, abstract = {It is well known that bilevel optimization problems are hard to solve both in theory and practice. In this paper, we highlight a further computational difficulty when it comes to solving bilevel problems with continuous but nonconvex lower levels. Even if the lower-level problem is solved to ɛ-feasibility regarding its nonlinear constraints for an arbitrarily small but positive ɛ, the obtained bilevel solution as well as its objective value may be arbitrarily far away from the actual bilevel solution and its actual objective value. This result even holds for bilevel problems for which the nonconvex lower level is uniquely solvable, for which the strict complementarity condition holds, for which the feasible set is convex, and for which Slater's constraint qualification is satisfied for all feasible upper-level decisions. Since the consideration of ɛ-feasibility cannot be avoided when solving nonconvex problems to global optimality, our result shows that computational bilevel optimization with continuous and nonconvex lower levels needs to be done with great care. Finally, we illustrate that the nonlinearities in the lower level are the key reason for the observed bad behavior by showing that linear bilevel problems behave much better at least on the level of feasible solutions.}, language = {en} }