TY - JOUR A1 - Krug, Richard A1 - Leugering, Günter A1 - Martin, Alexander A1 - Schmidt, Martin A1 - Weninger, Dieter T1 - Time-Domain Decomposition for Optimal Control Problems Governed by Semilinear Hyperbolic Systems with Mixed Two-Point Boundary Conditions JF - Control and Cybernetics N2 - In this article, we continue our work (Krug et al., 2021) on time-domain decomposition of optimal control problems for systems of semilinear hyperbolic equations in that we now consider mixed two-point boundary value problems and provide an in-depth well-posedness analysis. The more general boundary conditions significantly enlarge the scope of applications, e.g., to hyperbolic problems on metric graphs with cycles. We design an iterative method based on the optimality systems that can be interpreted as a decomposition method for the original optimal control problem into virtual control problems on smaller time domains. KW - Time-domain decomposition KW - Optimal control KW - Semilinear hyperbolic systems KW - Convergence Y1 - 2021 ER - TY - JOUR A1 - Kleinert, Thomas A1 - Manns, Julian A1 - Schmidt, Martin A1 - Weninger, Dieter T1 - Presolving Linear Bilevel Optimization Problems JF - EURO Journal on Computational Optimization N2 - Linear bilevel optimization problems are known to be strongly NP-hard and the computational techniques to solve these problems are often motivated by techniques from single-level mixed-integer optimization. Thus, during the last years and decades many branch-and-bound methods, cutting planes, or heuristics have been proposed. On the other hand, there is almost no literature on presolving linear bilevel problems although presolve is a very important ingredient in state-of-the-art mixed-integer optimization solvers. In this paper, we carry over standard presolve techniques from single-level optimization to bilevel problems and show that this needs to be done with great caution since a naive application of well-known techniques does often not lead to correctly presolved bilevel models. Our numerical study shows that presolve can also be very beneficial for bilevel problems but also highlights that these methods have a more heterogeneous effect on the solution process compared to what is known from single-level optimization. As a side result, our numerical experiments reveal that there is an urgent need for better and more heterogeneous test instance libraries to further propel the field of computational bilevel optimization. KW - Linear Bilevel Optimization KW - Presolve KW - Computational Analysis Y1 - 2021 U6 - https://doi.org/10.1016/j.ejco.2021.100020 IS - 9 ER - TY - JOUR A1 - Krug, Richard A1 - Leugering, Günter A1 - Martin, Alexander A1 - Schmidt, Martin A1 - Weninger, Dieter T1 - Time-Domain Decomposition for Optimal Control Problems Governed by Semilinear Hyperbolic Systems JF - SIAM Journal on Control and Optimization N2 - In this article, we extend the time-domain decomposition method described by Lagnese and Leugering (2003) to semilinear optimal control problems for hyperbolic balance laws with spatio-temporal varying coefficients. We provide the design of the iterative method applied to the global first-order optimality system, prove its convergence, and derive an a posteriori error estimate. The analysis is done entirely on the continuous level. A distinguishing feature of the method is that the decomposed optimality system can be interpreted as an optimality system of a local "virtual" optimal control problem. Thus, the iterative time-domain decomposition of the optimality system can be interpreted as an iterative parallel scheme for virtual optimal control problems on the subintervals. A typical example and further comments are given to show the range of potential applications. Moreover, we provide some numerical experiments to give a first interpretation of the role of the parameters involved in the iterative process. KW - Time-domain decomposition KW - Optimal control KW - Semilinear hyperbolic systems KW - Convergence KW - A posteriori error estimates Y1 - 2020 ER - TY - JOUR A1 - Bärmann, Andreas A1 - Liers, Frauke A1 - Martin, Alexander A1 - Merkert, Maximilian A1 - Thurner, Christoph A1 - Weninger, Dieter T1 - Solving network design problems via iterative aggregation JF - Mathematical Programming Computation N2 - In this work, we present an exact approach for solving network design problems that is based on an iterative graph aggregation procedure. The scheme allows existing preinstalled capacities. Starting with an initial aggregation, we solve a sequence of network design master problems over increasingly fine-grained representations of the original network. In each step, a subproblem is solved that either proves optimality of the solution or gives a directive where to refine the representation of the network in the subsequent iteration. The algorithm terminates with a globally optimal solution to the original problem. Our implementation uses a standard integer programming solver for solving the master problems as well as the subproblems. The computational results on random and realistic instances confirm the profitable use of the iterative aggregation technique. The computing time often reduces drastically when our method is compared to solving the original problem from scratch. KW - Aggregation KW - Network design KW - Combinatorial optimization KW - Mixed-integer programming KW - Branch-and-cut Y1 - 2015 U6 - https://doi.org/10.1007/s12532-015-0079-1 VL - 7 IS - 2 SP - 189 EP - 217 ER - TY - INPR A1 - Halbig, Katrin A1 - Hümbs, Lukas A1 - Rösel, Florian A1 - Schewe, Lars A1 - Weninger, Dieter T1 - Computing optimality certificates for convex mixed-integer nonlinear problems N2 - Every optimization problem has a corresponding verification problem which verifies whether a given optimal solution is in fact optimal. In the literature there are a lot of such ways to verify optimality for a given solution, e.g., the branch-and-bound tree. To simplify this task, Baes et al. introduced optimality certificates for convex mixed-integer nonlinear programs and proved that these are bounded in the number of integer variables. We introduce an algorithm to compute the certificates and conduct computational experiments. Through the experiments we show that the optimality certificates can be surprisingly small. Y1 - 2021 ER - TY - INPR A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Weninger, Dieter T1 - A Decomposition Heuristic for Mixed-Integer Supply Chain Problems T2 - Operations Research Letters N2 - Mixed-integer supply chain models typically are very large but are also very sparse and can be decomposed into loosely coupled blocks. In this paper, we use general-purpose techniques to obtain a block decomposition of supply chain instances and apply a tailored penalty alternating direction method, which exploits the structural properties of the decomposed instances. We further describe problem-specific enhancements of the algorithm and present numerical results on real-world instances that illustrate the applicability of the approach. KW - Supply chain KW - Mixed-integer optimization KW - Decomposition KW - Penalty method KW - Alternating direction methods Y1 - 2019 IS - 48(3) SP - 225 EP - 232 ER - TY - INPR A1 - Krug, Richard A1 - Leugering, Günter A1 - Martin, Alexander A1 - Schmidt, Martin A1 - Weninger, Dieter T1 - A Consensus-Based Alternating Direction Method for Mixed-Integer and PDE-Constrained Gas Transport Problems N2 - 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 which may result in simpler classes of optimization problems since 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. KW - Gas transport networks KW - Mixed-integer nonlinear optimization KW - Alternating direction methods KW - Graph decomposition KW - Penalty methods Y1 - 2022 ER -