Friedrich-Alexander-Universität Erlangen-Nürnberg
Refine
Year of publication
Keywords
- Bilevel optimization (8)
- Optimal control (7)
- Gas networks (6)
- Uniqueness (6)
- Convergence (5)
- Networks (5)
- Robust optimization (5)
- robust optimization (5)
- Branch-and-cut (4)
- Mixed-Integer Nonlinear Optimization (4)
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.
We study optimal control problems for linear systems with prescribed initial and terminal states. We analyze the exact penalization of the terminal constraints. We show that for systems that are exactly controllable, the norm-minimal exact control can be computed as the solution of an optimization problem without terminal constraint but with a nonsmooth penalization of the end conditions in the objective function, if the penalty parameter is sufficiently large. We describe the application of the method for hyperbolic and parabolic systems of partial differential equations, considering the wave and heat equations as particular examples. Copyright © 2016 John Wiley & Sons, Ltd.
We consider optimal control problems for the flow of gas or fresh water in pipe networks as well as drainage or sewer systems in open canals. The equations of motion are taken to be represented by the nonlinear isothermal Euler gas equations, the water hammer equations, or the St.~Venant equations for flow. We formulate model hierarchies and derive an abstract model for such network flow problems including pipes, junctions, and controllable elements such as valves, weirs, pumps, as well as compressors. We use the abstract model to give an overview of the known results and challenges concerning equilibria, well-posedness, controllability, and optimal control. A major challenge concerning the optimization is to deal with switching on-off states that are inherent to controllable devices in such applications combined with
continuous simulation and optimization of the gas flow. We formulate the corresponding mixed-integer nonlinear optimal control problems and outline a decomposition approach as a solution technique.
Nonconvex mixed-binary nonlinear optimization problems frequently appear in practice and are typically extremely hard to solve. In this paper we discuss a class of primal heuristics that are based on a reformulation of the problem as a mathematical program with equilibrium constraints. We then use different regularization schemes for this class of problems and use an iterative solution procedure for solving series of regularized problems. In the case of success, these procedures result in a feasible solution of the original mixed-binary nonlinear problem. Since we rely on local nonlinear programming solvers the resulting method is fast and we further improve its reliability by additional algorithmic techniques. We show the strength of our method by an extensive computational study on 662 MINLPLib2 instances, where our methods are able to produce feasible solutions for 60% of all instances in at most 10s.
We consider a system of scalar nonlocal conservation laws on networks that model a highly re-entrant multi-commodity manufacturing system as encountered in semiconductor production. Every single commodity is mod-eled by a nonlocal conservation law, and the corresponding PDEs are coupled via a collective load, the work in progress. We illustrate the dynamics for two commodities. In the applications, directed acyclic networks naturally occur, therefore this type of networks is considered. On every edge of the network we have a system of coupled conservation laws with nonlocal velocity. At the junctions the right hand side boundary data of the foregoing edges is passed as left hand side boundary data to the following edges and PDEs. For distributing junctions, where we have more than one outgoing edge, we impose time dependent distribution functions that guarantee conservation of mass. We provide results of regularity, existence and well-posedness of the multi-commodity network model for L p-, BV-and W 1,p-data. Moreover, we define an L 2-tracking type objective and show the existence of minimizers that solve the corresponding optimal control problem.
In optimal control loops delays can occur, for example through transmission via digital communication channels. Such delays influence the state that is generated by the implemented control. We study the effect of a delay in the implementation of L 2-norm minimal Neumann boundary controls for the wave equation. The optimal controls are computed as solutions of problems of exact optimal control, that is if they are implemented without delay, they steer the system to a position of rest in a given finite time T. We show that arbitrarily small delays δ > 0 can have a destabilizing effect in the sense that we can find initial states such that if the optimal control u is implemented in the form yx(t, 1) = u(t − δ) for t > δ, the energy of the system state at the terminal time T is almost twice as big as the initial energy. We also show that for more regular initial states, the effect of a delay in the implementation of the optimal control is bounded above in the sense that for initial positions with derivatives of BV-regularity and initial velocities with BV-regularity, the terminal energy is bounded above by the delay δ multiplied with a factor that depends on the BV-norm of the initial data. We show that for more general hyperbolic optimal exact control problems the situation is similar. For systems that have arbitrarily large eigenvalues, we can find terminal times T and arbitrarily small time delays δ, such that at the time T + δ, in the optimal control loop with delay the norm of the state is twice as large as the corresponding norm for the initial state. Moreover, if the initial state satisfies an additional regularity condition, there is an upper bound for the effect of time delay of the order of the delay with a constant that depends on the initial state only.
For the management of gas transportation networks, it is essential to know how the stationary states of the system are determined by the boundary data. The isothermal Euler equations are an accurate pde-model for the gas flow through each pipe. A compressibility factor is used to model the nonlinear relationship between density and pressure that occurs in real gas in contrast to ideal gas. The gas flow through the nodes is governed by algebraic node conditions that require the conservation of mass and the continuity of the pressure. We examine networks that are described by arbitrary finite graphs and show that for suitably chosen boundary data, subsonic stationary states exist and are uniquely determined by the boundary data. Our construction of the stationary states is based upon explicit representations of the stationary states on each single pipe that can easily be evaluated numerically. We also use the monotonicity properties of these states as functions of the boundary data.
In this work we study polyhedra in the context of network flow problems, where the flow value on each arc lies in one of several predefined intervals. This is motivated by nonlinear
problems on transportation networks, where nonlinearities are handled by piecewise linear approximation or relaxation - a common and established approach in many applications.
Several methods for modeling piecewise linear functions are known which provide a complete description for a single network arc. However, in general this property is lost when considering multiple arcs. We show how to strengthen the formulation for specific substructures consisting of multiple arcs by linear inequalities. For the case of paths of degree-two-nodes we give a complete description of the polyhedron projected to the integer variables. Our model is based on - but not limited to - the multiple choice method; we also show how to transfer our results to a formulation based on the incremental method. Computational results show that a state-of-the-art MIP-solver greatly benefits from using our cutting planes for random and realistic network topologies.
We consider the clique problem with multiple-choice constraints (CPMC) and characterize a case where it is possible to give an efficient description of the convex hull of its feasible solutions. This case, which we call staircase compatibility, generalizes common properties in applications and allows for a linear description of the integer feasible solutions to (CPMC) with a totally unimodular constraint matrix
of polynomial size. We derive two such totally unimodular reformulations for the problem: one that is obtained by a strengthening of the compatibility constraints
and one that is based on a representation as a dual network flow problem. Furthermore, we show a natural way to derive integral solutions from fractional solutions to the problem by determining integral extreme points generating this fractional
solution. We also evaluate our reformulations from a computational point of view by applying them to two different real-world applications. The first one is
a problem in railway timetabling where we try to adapt a given timetable slightly such that energy costs from operating the trains are reduced. The second one is the piecewise linearization of non-linear flow problems on a gas network. In both cases, we are able to reduce the solution times significantly by passing to the theoretically stronger formulations of the problem.
We consider traffic flow governed by the LWR model. We show that a Lipschitz continuous initial density with free-flow and sufficiently small Lipschitz constant can be controlled exactly to an arbitrary constant free-flow density in finite time by a piecewise linear boundary control function that controls the density at the inflow boundary if the outflow boundary is absorbing. Moreover, this can be done in such a way that the generated state is Lipschitz continuous. Since the target states need not be close to the initial state, our result is a global exact controllability result. The Lipschitz constant of the generated state can be made arbitrarily small if the Lipschitz constant of the initial density is sufficiently small and the control time is sufficiently long. This is motivated by the idea that finite or even small Lipschitz constants are desirable in traffic flow since they might help to decrease the speed variation and lead to safer traffic.
We consider the problem of boundary feedback stabilization of a vibrating string that is fixed at one end and with control action at the other end. In contrast to previous studies that have required L 2-regularity for the initial position and H −1-regularity for the initial velocity, in this paper we allow for initial positions with L 1-regularity and initial velocities in W −1,1 on the space interval. It is well known that for a certain feedback parameter, for sufficiently regular initial states the classical energy of the closed-loop system with Neumann velocity feedback is controlled to zero after a finite time that is equal to the minimal time where exact controllability holds. In this paper, we present a Dirichlet boundary feedback that yields a well-defined closed-loop system in the (L 1 , W −1,1) framework and also has this property. Moreover, for all positive feedback parameters our feedback law leads to exponential decay of a suitably defined L 1-energy. For more regular initial states with (L 2 , H −1) regularity, the proposed feedback law leads to exponential decay of an energy that corresponds to this framework. If the initial states are even more regular with H 1-regularity of the initial position and L 2-regularity of the initial velocity, our feedback law also leads to exponential decay of the classical energy.
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á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.
A Decomposition Approach for Optimum Gas Network Extension with a Finite Set of Demand Scenarios
(2016)
Today's gas markets demand more flexibility from the network operators which in turn have to invest into their network infrastructure. As these investments are very cost-intensive and long-living, network extensions should not only focus on a single bottleneck scenario, but should increase the flexibility to fulfill different demand scenarios. In this work, we formulate a model for the network extension problem for multiple demand scenarios and propose a scenario decomposition in order to solve the arising challenging optimization tasks. In fact, euch subproblem consists of a mixed-integer nonlinear optimization problem (MINLP). Valid bounds are derived even without solving the subproblems to optimality. Furthermore, we develop heuristics that prove capable of improving the initial solutions substantially. Results of computational experiments on realistic network topologies are presented. It turns out that our method is able to solve these challenging instances to optimality within a reasonable amount of time.
Detailed modeling of gas transport problems leads to nonlinear
and nonconvex mixed-integer optimization or feasibility models
(MINLPs) because both the incorporation of discrete controls of the
network as well as accurate physical and technical modeling is
required in order to achieve practical solutions. Hence, ignoring
certain parts of the physics model is not valid for practice. In the
present contribution we extend an approach based on linear relaxations
of the underlying nonlinearities by tailored model reformulation
techniques yielding block-separable MINLPs. This combination of
techniques allows us to apply a penalty alternating direction method
and thus to solve highly detailed MINLPs for large-scale real-world
instances. The practical strength of the proposed method is
demonstrated by a computational study in which we apply the method to
instances from steady-state gas transport
including both pooling effects with respect to the mixing of gases of
different composition and a highly detailed compressor station model.
We propose an equilibrium model that allows to analyze the long-run impact of the electricity market design on transmission line expansion by the regulator and investment in generation capacity by private firms in liberalized electricity markets. The model incorporates investment decisions of the transmission system operator and private firms in expectation of an energy-only market and cost-based redispatch. In different specifications we consider the cases of one vs. multiple price zones (market splitting) and analyze different approaches to recover network cost—in particular lump sum, generation capacity based, and energy based fees. In order to compare the outcomes of our multilevel market model with a first best benchmark, we also solve the corresponding integrated planner problem. Using two test networks we illustrate that energy-only markets can lead to suboptimal locational decisions for generation capacity and thus imply excessive network expansion. Market splitting heals these problems only partially. These results are valid for all considered types of network tariffs, although investment slightly differs across those regimes.
We consider a vibrating string that is fixed at one end with Neumann control action at the other end. We investigate the optimal control problem of steering this system from given initial data to rest, in time TT, by minimizing an objective functional that is the convex sum of the L2L2-norm of the control and of a boundary Neumann tracking term.
We provide an explicit solution of this optimal control problem, showing that if the weight of the tracking term is positive, then the optimal control action is concentrated at the beginning and at the end of the time interval, and in-between it decays exponentially. We show that the optimal control can actually be written in that case as the sum of an exponentially decaying term and of an exponentially increasing term. This implies that, if the time TT is large, then the optimal trajectory approximately consists of three arcs, where the first and the third short-time arcs are transient arcs, and in the middle arc the optimal control and the corresponding state are exponentially close to 00. This is an example of a turnpike phenomenon for a problem of optimal boundary control. If T=+∞T=+∞ (infinite time horizon problem), then only the exponentially decaying component of the control remains, and the norms of the optimal control action and of the optimal state decay exponentially in time. In contrast to this situation, if the weight of the tracking term is zero and only the control cost is minimized, then the optimal control is distributed uniformly along the whole interval [0,T][0,T] and coincides with the control given by the Hilbert Uniqueness Method.
In addition, we establish a similarity theorem stating that, for every T>0T>0, there exists an appropriate weight λ<1λ<1 for which the optimal solutions of the corresponding finite horizon optimal control problem and of the infinite horizon optimal control problem coincide along the first part of the time interval [0,2][0,2]. We also discuss the turnpike phenomenon from the perspective of a general framework with a strongly continuous semi-group.
Finite Time Blow-up of Traveling Wave Solutions for the Flow of Real Gas through Pipeline Networks
(2016)
In the context of gas transportation, analytical solutions are essential
for the understanding of the underlying dynamics described
by a system of partial differential equations. We derive traveling wave
solutions for the 1-d isothermal Euler equations. A non-constant compressibility
factor is used to describe the correlation between density
and pressure. The blow-up of the traveling wave solution in finite time
is proven. We then extend our analysis to networks under appropriate
coupling conditions and derive compatibility conditions to fulfill these
coupling conditions.