Because of 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 problem, we present heuristic methods that are based on the solution of a linear number of problems of the nominal type. Moreover, quality guarantees for heuristically obtained solutions as well as sufficient ex-post conditions for global optimality of the outcomes are provided. In an extensive computational study on 2,240 instances, we assess the performance of our heuristics and compare them with alternative methods—both heuristic and exact—from the literature. We observe that the optimality gap is closed for a significant portion of the considered instances and that our methods often practically outperform alternative approaches in terms of the solution quality. Moreover, for the special case of Γ-robust interdiction problems, we report considerable speed-up factors when compared with recently published problem-tailored and exact solution approaches while also solving more instances to global optimality. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0239 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0239 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Abstract We study bilevel problems with a convex quadratic mixed-integer upper-level, integer linking variables, and a nonconvex quadratic, purely continuous lower-level problem. We prove $$\Sigma _2^p$$ Σ 2 p -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 this end, we make use of the Karush–Kuhn–Tucker conditions of the lower-level problem for the lower-bounding step, since these conditions are only necessary but not sufficient in our setting. Moreover, integer no-good cuts as well as a simple optimality cut are used to obtain finiteness of the method. Finally, we illustrate the applicability of our approach by the first large-scale numerical experiment for this class of problems in the literature.

Abstract We propose a framework that allows to quantitatively analyze the interplay of the different agents involved in gas trade and transport in the context of the European entry-exit system. Previous contributions have focused on the case of perfectly competitive buyers and sellers of gas, which allows to replace the respective market equilibrium problem by a single welfare maximization problem. Our novel framework considers the mathematically more challenging case of a monopolistic and thus strategic gas seller. In this framework, the objective functions of the gas sellers and buyers cannot be aggregated into a common objective function, which is why a multilevel formulation is necessary to accurately capture the sequential nature of the decisions taken. For this setup, we derive sufficient conditions that allow for reformulating the challenging four-level model as a computationally tractable single-level reformulation. We prove the correctness of this reformulation and use it for solving several test instances to illustrate the applicability of our approach.

We consider mixed-integer linear quantile minimization problems that yield large-scale problems that are very hard to solve for real-world instances. We motivate the study of this problem class by two important real-world problems: a maintenance planning problem for electricity networks and a quantile-based variant of the classic portfolio optimization problem. For these problems, we develop valid inequalities and present an overlapping alternating direction method. Moreover, we discuss an adaptive scenario clustering method for which we prove that it terminates after a finite number of iterations with a global optimal solution. We study the computational impact of all presented techniques and finally show that their combination leads to an overall method that can solve the maintenance planning problem on large-scale real-world instances provided by the ROADEF/EURO challenge 2020 1 and that they also lead to significant improvements when solving a quantile-version of the classic portfolio optimization problem. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by the Deutsche Forschungsgemeinschaft [CRC TRR 154], Fonds De La Recherche Scientifique [PDR T0098.18], and Bundesministerium für Bildung und Forschung. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.0105 .

We consider dynamic gas transport optimization problems, which lead to large-scale and nonconvex mixed-integer nonlinear optimization problems (MINLPs) on graphs. Usually, the resulting instances are too challenging to be solved by state-of-the-art MINLP solvers. In this paper, we use graph decompositions to obtain multiple optimization problems on smaller blocks, which can be solved in parallel and may result in simpler classes of optimization problems because not every block necessarily contains mixed-integer or nonlinear aspects. For achieving feasibility at the interfaces of the several blocks, we employ a tailored consensus-based penalty alternating direction method. Our numerical results show that such decomposition techniques can outperform the baseline approach of just solving the overall MINLP from scratch. However, a complete answer to the question of how to decompose MINLPs on graphs in dependence of the given model is still an open topic for future research. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by Deutsche Forschungsgemeinschaft [Grant TRR 154].

Abstract The minimum sum-of-squares clustering problem is a very important problem in data mining and machine learning with very many applications in, e.g., medicine or social sciences. However, it is known to be NP-hard in all relevant cases and to be notoriously hard to be solved to global optimality in practice. In this paper, we develop and test different tailored mixed-integer programming techniques to improve the performance of state-of-the-art MINLP solvers when applied to the problem—among them are cutting planes, propagation techniques, branching rules, or primal heuristics. Our extensive numerical study shows that our techniques significantly improve the performance of the open-source MINLP solver . Consequently, using our novel techniques, we can solve many instances that are not solvable with without our techniques and we obtain much smaller gaps for those instances that can still not be solved to global optimality.

Cardinality-constrained optimization problems are notoriously hard to solve in both theory and practice. However, as famous examples, such as the sparse portfolio optimization and best subset selection problems, show, this class is extremely important in real-world applications. In this paper, we apply a penalty alternating direction method to these problems. The key idea is to split the problem along its discrete-continuous structure to obtain two subproblems that are much easier to solve than the original problem. In addition, the coupling between these subproblems is achieved via a classic penalty framework. The method can be seen as a primal heuristic for which convergence results are readily available from the literature. In our extensive computational study, we first show that the method is competitive to a commercial mixed-integer program solver for the portfolio optimization problem. On these instances, we also test a variant of our approach that uses a perspective reformulation of the problem. Regarding the best subset selection problem, it turns out that our method significantly outperforms commercial solvers and it is at least competitive to state-of-the-art methods from the literature. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: The first author thanks the Deutsche Forschungsgemeinschaft (DFG) for its support within “Algorithmic Optimization” [Grant RTG 2126]. The third author thanks the DFG for its support within project A05 and B08 in the “Sonderforschungsbereich/Transregio 154 Mathematical Modeling, Simulation and Optimization using the Example of Gas Networks.” Supplemental Material: The supplementary material is available at https://doi.org/10.1287/ijoc.2022.1211 .

Linear complementarity problems (LCPs) are an important modeling tool for many practically relevant situations and also have many important applications in mathematics itself. Although the continuous version of the problem is extremely well-studied, much less is known about mixed-integer LCPs (MILCPs) in which some variables have to be integer-valued in a solution. In particular, almost no tailored algorithms are known besides reformulations of the problem that allow us to apply general purpose mixed integer linear programming solvers. In this paper, we present, theoretically analyze, enhance, and test a novel branch-and-bound method for MILCPs. The main property of this method is that we do not “branch” on constraints as usual but by adding suitably chosen penalty terms to the objective function. By doing so, we can either provably compute an MILCP solution if one exists or compute an approximate solution that minimizes an infeasibility measure combining integrality and complementarity conditions. We enhance the method by MILCP-tailored valid inequalities, node selection strategies, branching rules, and warm-starting techniques. The resulting algorithm is shown to clearly outperform two benchmark approaches from the literature. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: M. De Santis acknowledges support within the project RM120172A2970290, which has received funding from Sapienza, University of Rome. M. Schmidt thanks the Deutsche Forschungsgemeinschaft (DFG) for its support within project A05 and B08 in the “SFB TRR 154 Mathematical Modelling, Simulation and Optimization using the Example of Gas Networks.” L. Winkel is supported by the DFG within the Research Training Group 2126: “Algorithmic Optimization.” Supplemental Material: The online supplementary material is available at https://doi.org/10.1287/ijoc.2022.1216 .

Abstract Bilevel optimization is an increasingly important tool to model hierarchical decision making. However, the ability of modeling such settings makes bilevel problems hard to solve in theory and practice. In this paper, we add on the general difficulty of this class of problems by further incorporating convex black-box constraints in the lower level. For this setup, we develop a cutting-plane algorithm that computes approximate bilevel-feasible points. We apply this method to a bilevel model of the European gas market in which we use a joint chance constraint to model uncertain loads. Since the chance constraint is not available in closed form, this fits into the black-box setting studied before. For the applied model, we use further problem-specific insights to derive bounds on the objective value of the bilevel problem. By doing so, we are able to show that we solve the application problem to approximate global optimality. In our numerical case study we are thus able to evaluate the welfare sensitivity in dependence of the achieved safety level of uncertain load coverage.

Abstract The European gas market is implemented as an entry-exit system, which aims to decouple transport and trading of gas. It has been modeled in the literature as a multilevel problem, which contains a nonlinear flow model of gas physics. Besides the multilevel structure and the nonlinear flow model, the computation of so-called technical capacities is another major challenge. These lead to nonlinear adjustable robust constraints that are computationally intractable in general. We provide techniques to equivalently reformulate these nonlinear adjustable constraints as finitely many convex constraints including integer variables in the case that the underlying network is tree-shaped. We further derive additional combinatorial constraints that significantly speed up the solution process. Using our results, we can recast the multilevel model as a single-level nonconvex mixed-integer nonlinear problem, which we then solve on a real-world network, namely the Greek gas network, to global optimality. Overall, this is the first time that the considered multilevel entry-exit system can be solved for a real-world sized network and a nonlinear flow model.

Bilevel problems are highly challenging optimization problems that appear in many applications of energy market design, critical infrastructure defense, transportation, pricing, and so on. Often these bilevel models are equipped with integer decisions, which makes the problems even harder to solve. Typically, in such a setting in mathematical optimization, one develops primal heuristics in order to obtain feasible points of good quality quickly or to enhance the search process of exact global methods. However, there are comparably few heuristics for bilevel problems. In this paper, we develop such a primal heuristic for bilevel problems with a mixed-integer linear or quadratic upper level and a linear or quadratic lower level. The heuristic is based on a penalty alternating direction method, which allows for a theoretical analysis. We derive a convergence theory stating that the method converges to a stationary point of an equivalent single-level reformulation of the bilevel problem and extensively test the method on a test set of more than 2,800 instances—which is one of the largest computational test sets ever used in bilevel programming. The study illustrates the very good performance of the proposed method in terms of both running times and solution quality. This renders the method a suitable subroutine in global bilevel solvers as well as a reasonable standalone approach.Summary of Contribution: Bilevel optimization problems form a very important class of optimization problems in the field of operations research, which is mainly due to their capability of modeling hierarchical decision processes. However, real-world bilevel problems are usually very hard to solve—especially in the case in which additional mixed-integer aspects are included in the modeling. Hence, the development of fast and reliable primal heuristics for this class of problems is very important. This paper presents such a method.

Abstract We show that the feasibility of a booking in the European entry‐exit gas market can be decided in polynomial time on single‐cycle networks that are passive, i.e., do not contain controllable elements. The feasibility of a booking can be characterized by solving polynomially many nonlinear potential‐based flow models for computing so‐called potential‐difference maximizing load flow scenarios. We thus analyze the structure of these models and exploit both the cyclic graph structure as well as specific properties of potential‐based flows. This enables us to solve the decision variant of the nonlinear potential‐difference maximization by reducing it to a system of polynomials of constant dimension that is independent of the cycle's size. This system of fixed dimension can be handled with tools from real algebraic geometry to derive a polynomial‐time algorithm. The characterization in terms of potential‐difference maximizing load flow scenarios then leads to a polynomial‐time algorithm for deciding the feasibility of a booking. Our theoretical results extend the existing knowledge about the complexity of deciding the feasibility of bookings from trees to single‐cycle networks.

Abstract Potential‐based flows are an extension of classical network flows in which the flow on an arc is determined by the difference of the potentials of its incident nodes. Such flows are unique and arise, for example, in energy networks. Two important algorithmic problems are to determine whether there exists a feasible flow and to maximize the flow between two designated nodes. We show that these problems can be solved for the single source and sink case by reducing the network to a single arc. However, if we additionally consider switches that allow to force the flow to 0 and decouple the potentials, these problems are NP‐hard. Nevertheless, for particular series‐parallel networks, one can use algorithms for the subset sum problem. Moreover, applying network presolving based on generalized series‐parallel structures allows to significantly reduce the size of realistic energy networks.

We propose a decomposition based method for solving mixed‐integer nonlinear optimization problems with “black‐box” nonlinearities, where the latter, for example, may arise due to differential equations or expensive simulation runs. The method alternatingly solves a mixed‐integer linear master problem and a separation problem for iteratively refining the mixed‐integer linear relaxation of the nonlinear equalities. The latter yield nonconvex feasible sets for the optimization model but we have to restrict ourselves to convex and monotone constraint functions. Under these assumptions, we prove that our algorithm finitely terminates with a global optimal solution of the mixed‐integer nonlinear problem. Additionally, we show the applicability of our approach for three applications from optimal control with integer variables, from the field of pressurized flows in pipes with elastic walls, and from steady‐state gas transport. For the latter we also present promising numerical results of our method applied to real‐world instances that particularly show the effectiveness of our method for problems defined on networks.

Multistage stochastic optimization leads to NLPs over scenario trees that become extremely large when many time stages or fine discretizations of the probability space are required. Interior-point methods are well suited for these problems if the arising huge, structured KKT systems can be solved efficiently, for instance, with a large scenario tree but a moderate number of variables per node. For this setting we develop a distributed implementation based on data parallelism in a depth-first distribution of the scenario tree over the processes. Our theoretical analysis predicts very low memory and communication overheads. Detailed computational experiments confirm this prediction and demonstrate the overall performance of the algorithm. We solve multistage stochastic quadratic programs with up to 400 × 106 variables and 8.59 × 109 KKT matrix entries or 136 × 106 variables and 12.6 × 109 entries on a compute cluster with 384 GB RAM. Data are available at https://doi.org/10.1287/ijoc.2017.0748 .