JTJohannes Thürauf

Johannes Thürauf

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Johannes Thürauf has a total of 25 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Potential-Based Flows – An Overview

    by Marc E. Pfetsch, Martin Schmidt, Martin Skutella, Johannes Thürauf

  • Open Access

    Mixed-Integer Nonlinear Optimization in the Context of Gas Networks

    by Robert Burlacu, Adrian Göß, Günter Leugering, Alexander Martin, Marc E. Pfetsch, Martin Schmidt, Johannes Thürauf

  • Open Access

    On Coupling Constraints in Pessimistic Linear Bilevel Optimization

    by Dorothee Henke, Henri Lefebvre, Martin Schmidt, Johannes Thürauf

    The literature on pessimistic linear bilevel optimization with coupling constraints is rather scarce and it has been common sense that these problems are harder to tackle than pessimistic bilevel problems without coupling constraints. In this note, we show that this is not the case. To this end, given a pessimistic problem with coupling constraints, we derive a pessimistic problem without coupling constraints that has the same set of globally optimal solutions. Moreover, our results also show that one can equivalently replace a pessimistic problem with such constraints with an optimistic problem without coupling constraints. This paves the way of both transferring theory and solution techniques from any type of these problems to any other one.


  • Open Access

    Column generation in column-and-constraint generation for adjustable robust optimization with Interdiction-type linking Constraints

    by Henri Lefebvre, Martin Schmidt, Johannes Thürauf

    Adjustable robust optimization (ARO) is a powerful tool to model problems that have uncertain data and that feature a two-stage decision-making process. Computationally, they are often addressed using the column-and-constraint generation (CCG) algorithm introduced by Zeng and Zhao [45]. While it was empirically shown that the algorithm scales well if all second-stage decisions are continuous, the presence of integer variables in the second stage rapidly leads to challenging large-scale mixed-integer problems within CCG. These problems can no longer be solved to global optimality within reasonable time limits in general. In this work, we explicitly focus on ARO problems with mixed-integer second-stage decisions and discuss the main difficulties of successfully applying CCG to this problem class. We then introduce, for a large set of problems with specific structural properties, a stronger formulation, which can be used in place of the master problem in the classic CCG algorithm. We show how this model can be effectively solved by column generation (CG). Additionally, we introduce a new CG-based heuristic that is able to generate new feasible points to speed up the overall method. We apply this nested scheme, combining CCG and CG, to three problems from logistics and scheduling to show the applicability of our approach.


  • Open Access

    Learning the follower’s objective function in sequential bilevel games

    by Ioana Molan, Martin Schmidt, Johannes Thürauf

    We consider bilevel optimization problems in which the leader has no or only partial knowledge about the objective function of the follower. The studied setting is a sequential one in which the bilevel game is played repeatedly. This allows the leader to learn the objective function (values) of the follower over time. We focus on two methods: a multiplicative weight update (MWU) method and one based on the lower-level’s KKT conditions that are used in the sense of inverse optimization. The MWU method requires less assumptions but the convergence guarantee is also only on the follower’s objective function values, whereas the inverse KKT method requires stronger assumptions but actually allows to learn objective functions that are consistent with the already observed interactions between the two players. Although the theory we present is only related to the lower-level and not to the upper-level problem, we show that the gained information are practically useful for the leader by illustrating that, over time, the leader’s objective function values tend to those that would be obtained under full information. The applicability of the proposed methods is shown using two case studies. First, we study a repeatedly played continuous knapsack interdiction problem and, second, a sequential bilevel pricing game in which the leader needs to learn the utility function of the follower. For both problems, we further illustrate the impact of this learning on the leader’s decisions.

  • Open Access

    Instance-Optimized String Fingerprints

    by Mihail Stoian, Johannes Thürauf, Andreas Zimmerer, Alexander van Renen, Andreas Kipf

    Recent research found that cloud data warehouses are text-heavy. However, their capabilities for efficiently processing string columns remain limited, relying primarily on techniques like dictionary encoding and prefix-based partition pruning. In recent work, we introduced string fingerprints - a lightweight secondary index structure designed to approximate LIKE predicates, albeit with false positives. This approach is particularly compelling for columnar query engines, where fingerprints can help reduce both compute and I/O overhead. We show that string fingerprints can be optimized for specific workloads using mixed-integer optimization, and that they can generalize to unseen table predicates. On an IMDb column evaluated in DuckDB v1.3, this yields table-scan speedups of up to 1.36$\times$.

  • Open Access

    Adjustable robust nonlinear network design without controllable elements under load scenario uncertainties

    by Johannes Thürauf, Julia Grübel, Martin Schmidt

    We study network design problems for nonlinear and nonconvex flow models without controllable elements under load scenario uncertainties, i.e., under uncertain injections and withdrawals. 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, load scenarios within a given uncertainty set. For solving the corresponding adjustable robust mixed-integer nonlinear optimization problem, we show that a given network design is robust feasible, i.e., it admits a feasible transport for all load scenario uncertainties, if and only if a finite number of worst-case load scenarios can be routed through the network. We compute these worst-case scenarios by solving polynomially many nonlinear optimization problems. Embedding this result for robust feasibility in an adversarial approach leads to an exact algorithm that computes an optimal robust network design in a finite number of iterations. Since all of the results are valid for general potential-based flows, the approach can be applied to different utility networks such as gas, hydrogen, or water networks. We finally demonstrate the applicability of the method by computing robust gas networks that are protected from future load fluctuations.


  • Open Access

    On coupling constraints in linear bilevel optimization

    by Dorothee Henke, Henri Lefebvre, Martin Schmidt, Johannes Thürauf

    It is well-known that coupling constraints in linear bilevel optimization can lead to disconnected feasible sets, which is not possible without coupling constraints. However, there is no difference between linear bilevel problems with and without coupling constraints w.r.t. their complexity-theoretical hardness. In this note, we prove that, although there is a clear difference between these two classes of problems in terms of their feasible sets, the classes are equivalent on the level of optimal solutions. To this end, given a general linear bilevel problem with coupling constraints, we derive a respective problem without coupling constraints and prove that it has the same optimal solutions (when projected back to the original variable space).


  • Open Access

    On a Computationally Ill-Behaved Bilevel Problem with a Continuous and Nonconvex Lower Level

    by Yasmine Beck, Daniel Bienstock, Martin Schmidt, Johannes Thürauf

    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 $$\varepsilon $$ ε -feasibility regarding its nonlinear constraints for an arbitrarily small but positive $$\varepsilon $$ ε , 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 $$\varepsilon $$ ε -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.


  • Open Access

    On a Computationally Ill-Behaved Bilevel Problem with a Continuous and Nonconvex Lower Level

    by Yasmine Beck, Daniel Bienstock, Martin Schmidt, Johannes Thürauf

    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 $\varepsilon$-feasibility regarding its nonlinear constraints for an arbitrarily small but positive $\varepsilon$, 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 $\varepsilon$-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.