A Consensus-Based Alternating Direction Method for Mixed-Integer and PDE-Constrained Gas Transport Problems - Krug, Richard; Leugering, Günter; Martin, Alexander; Schmidt, Martin; Weninger, Dieter (Informs Journal on Computing, 2024)
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.
CRIS-Team Scopus Importer:2025-02-04
Keywords: alternating-direction methods; gas transport networks; graph decomposition; mixed-integer nonlinear optimization; penalty methods

A Successive Linear Relaxation Method for MINLPs with Multivariate Lipschitz Continuous Nonlinearities - Grübel, Julia; Krug, Richard; Schmidt, Martin; Wollner, Winnifried (Journal of Optimization Theory and Applications, 2023)
We present a novel method for mixed-integer optimization problems with multivariate and Lipschitz continuous nonlinearities. In particular, we do not assume that the nonlinear constraints are explicitly given but that we can only evaluate them and that we know their global Lipschitz constants. The algorithm is a successive linear relaxation method in which we alternate between solving a master problem, which is a mixed-integer linear relaxation of the original problem, and a subproblem, which is designed to tighten the linear relaxation of the next master problem by using the Lipschitz information about the respective functions. By doing so, we follow the ideas of Schmidt, Sirvent, and Wollner (Math Program 178(1):449–483 (2019) and Optim Lett 16(5):1355-1372 (2022)) and improve the tackling of multivariate constraints. Although multivariate nonlinearities obviously increase modeling capabilities, their incorporation also significantly increases the computational burden of the proposed algorithm. We prove the correctness of our method and also derive a worst-case iteration bound. Finally, we show the generality of the addressed problem class and the proposed method by illustrating that both bilevel optimization problems with nonconvex and quadratic lower levels as well as nonlinear and mixed-integer models of gas transport can be tackled by our method. We provide the necessary theory for both applications and briefly illustrate the outcomes of the new method when applied to these two problems.
CRIS-Team Scopus Importer:2023-09-08
Keywords: Bilevel optimization; Gas networks; Global optimization; Lipschitz optimization; Mixed-integer nonlinear optimization

Nonlinear optimization of district heating networks - Krug, Richard; Mehrmann, Volker; Schmidt, Martin (Optimization and Engineering, 2020)
We develop a complementarity-constrained nonlinear optimization model for the time-dependent control of district heating networks. The main physical aspects of water and heat flow in these networks are governed by nonlinear and hyperbolic 1d partial differential equations. In addition, a pooling-type mixing model is required at the nodes of the network to treat the mixing of different water temperatures. This mixing model can be recast using suitable complementarity constraints. The resulting problem is a mathematical program with complementarity constraints subject to nonlinear partial differential equations describing the physics. In order to obtain a tractable problem, we apply suitable discretizations in space and time, resulting in a finite-dimensional optimization problem with complementarity constraints for which we develop a suitable reformulation with improved constraint regularity. Moreover, we propose an instantaneous control approach for the discretized problem, discuss practically relevant penalty formulations, and present preprocessing techniques that are used to simplify the mixing model at the nodes of the network. Finally, we use all these techniques to solve realistic instances. Our numerical results show the applicability of our techniques in practice.
CRIS-Team Scopus Importer:2020-09-25
Keywords: Complementarity constraints; Differential-algebraic equations; District heating networks; Euler equations; Mixing; Nonlinear optimization

Time-Domain Decomposition for Mixed-Integer Optimal Control Problems - Hante, Falk M.; Krug, Richard; Schmidt, Martin (Applied Mathematics and Optimization, 2023)
We consider mixed-integer optimal control problems, whose optimality conditions involve global combinatorial optimization aspects for the corresponding Hamiltonian pointwise in time. We propose a time-domain decomposition, which makes this problem class accessible for mixed-integer programming using parallel-in-time direct discretizations. The approach is based on a decomposition of the optimality system and the interpretation of the resulting subproblems as suitably chosen mixed-integer optimal control problems on subintervals in time. An iterative procedure then ensures continuity of the states at the boundaries of the subintervals via co-state information encoded in virtual controls. We prove convergence of this iterative scheme for discrete-continuous linear-quadratic problems and present numerical results both for linear-quadratic as well as nonlinear problems.
CRIS-Team Scopus Importer:2023-03-24
Keywords: Convergence; Mixed-integer nonlinear optimization; Mixed-integer optimal control problems; Time-domain decomposition

TIME-DOMAIN DECOMPOSITION FOR OPTIMAL CONTROL PROBLEMS GOVERNED BY SEMILINEAR HYPERBOLIC SYSTEMS - Krug, Richard; Leugering, Günter; Martin, Alexander; Schmidt, Martin; Weninger, Dieter (SIAM Journal on Control and Optimization, 2021)
In this article, we extend the time-domain decomposition method described by Lagnese and Leugering [Systems Control Lett., 48 (2003), pp. 229–242] to semilinear optimal control problems for hyperbolic balance laws with spatio-temp oral 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.
CRIS-Team WoS Importer:2022-01-07

Time-domain decomposition for optimal control problems governed by semilinear hyperbolic systems with mixed two-point boundary conditions∗ - Krug, Richard; Leugering, Günter; Martin, Alexander; Schmidt, Martin; Weninger, Dieter (Control and Cybernetics, 2021)
In this article, we study the time-domain decomposition of optimal control problems for systems of semilinear hyperbolic equations and provide an in-depth well-posedness analysis. This is a continuation of our work, Krug et al. (2021) in that we now consider mixed two-point boundary value problems. The more general boundary conditions signif-icantly enlarge the scope of applications, e.g., to hyperbolic problems on metric graphs with cycles. We design an iterative method based on the op-timality systems that can be interpreted as a decomposition method for the original optimal control problem into virtual control problems on smaller time domains.
CRIS-Team Scopus Importer:2024-12-16
Keywords: convergence; optimal control; semilinear hyperbolic systems; time-domain decomposition

Transient gas pipeline flow: analytical examples, numerical simulation and a comparison to the quasi-static approach - Gugat, Martin; Krug, Richard; Martin, Alexander (Optimization and Engineering, 2021)
The operation of gas pipeline flow with high pressure and small Mach numbers allows to model the flow by a semilinear hyperbolic system of partial differential equations. In this paper we present a number of transient and stationary analytical solutions of this model. They are used to discuss and clarify why a PDE model is necessary to handle certain dynamic situations in the operation of gas transportation networks. We show that adequate numerical discretizations can capture the dynamical behavior sufficiently accurate. We also present examples that show that in certain cases an optimization approach that is based on multi-period optimization of steady states does not lead to approximations that converge to the optimal state.<br
CRIS-Team Scopus Importer:2021-10-15
Keywords: isothermal Euler equations; gas pipeline flow; optimal control; quasi-static approach