Refine
Has Fulltext
- no (34) (remove)
Keywords
- Branch-and-cut (2)
- Combinatorial optimization (2)
- Networks (2)
- Aggregation (1)
- Boundary feedback control, feedback stabilization, exponential stability, isothermal Euler equations, second-order quasilinear equation, Lyapunov function, stationary state, non-stationary state, gas pipeline. (1)
- Complete description (1)
- Cut-set inequalities (1)
- Decomposition Method (1)
- Dynamic Network Flows (1)
- Dynamic Robust Flow (1)
In this paper we analyze peak-load pricing in the presence of network constraints. In our setup, firms facing fluctuating demand decide on the size and location of production facilities. They make production decisions constrained by the invested capacities, taking into account that market prices reflect scarce transmission capacities. We state general conditions for existence and uniqueness of the market equilibrium and provide a characterization of equilibrium investment and production. The presented analysis covers the cases of perfect competition and monopoly - the case of strategic firms is approximated by a conjectural variations approach. Our result is a prerequisite for analyzing regulatory policy options with computational multilevel equilibrium models, since uniqueness of the equilibrium at lower levels is of key importance when solving these models. Thus, our paper contributes to an evolving strand of literature that analyzes regulatory policy based on computational multilevel equilibrium models and aims at taking into account individual objectives of various agents, among them not only generators and customers but also, e.g., the regulator deciding on network expansion.
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 propose a decomposition based method for solving mixed-integer nonlinear optimization problems with “black-box” nonlinearities, where the latter, e.g., 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 an approximate feasible 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.
The economics of global green ammonia trade – "Shipping Australian wind and sunshine to Germany"
(2023)
This paper contributes to understanding the transformation of global energy trade to green energy carriers, focusing on green ammonia as the foreseeable first green hydrogen carrier. We provide a comprehensive overview of today's ammonia trade and assess scaling options for the trade of green ammonia. To that aim, we develop an optimization model for the integrated assessment of the green ammonia value chain that covers all steps from green ammonia production in an exporting country, up to delivery to a harbor in an importing country. The model endogenously chooses among different technology options and determines cost minimal operation. In a case study, we apply the model to the large-scale import of ammonia from Australia to Germany in a scenario for 2030. The results show that green ammonia can reach cost parity with gray ammonia even for moderate gas prices (but not necessarily with blue ammonia) if CO2 prices are high enough. We also provide a sensitivity analysis with respect to the interest rate and other key technical and economic parameters and show that cracking ammonia to provide pure hydrogen comes at a 45 % cost markup per MWh at the destination.
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 present a solution algorithm for problems from
steady-state gas transport optimization.
Due to nonlinear and nonconvex physics and engineering models as
well as discrete controllability of active network devices, these
problems lead to difficult nonconvex mixed-integer nonlinear optimization
models.
The proposed method is based on mixed-integer linear techniques using
piecewise linear relaxations of the nonlinearities and a tailored
alternating direction method.
Most other publications in the field of gas transport optimization only consider
pressure and flow as main physical quantities. In this work, we additionally
incorporate heat power supplies and demands as well as a mixing model for
different gas qualities.
We demonstrate the capabilities of our method on Germany's largest
transport networks and hereby present numerical results on the largest
instances that were ever reported in the literature for this problem
class.
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 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.
We study dynamic network flows with uncertain input data under a robust optimization perspective. In the dynamic maximum flow problem, the goal is to maximize the flow reaching the sink within a given time horizon T, while flow requires a certain travel time to traverse an arc. In our setting, we account for uncertain travel times of flow. We investigate maximum flows over time under the assumption that at most Γ travel times may be prolonged simultaneously due to delay. We develop and study a mathematical model for this problem. As the dynamic robust flow problem generalizes the static version, it is NP-hard to compute an optimal flow. However, our dynamic version is considerably more complex than the static version. We show that it is NP-hard to verify feasibility of a given candidate solution. Furthermore, we investigate temporally repeated flows and show that in contrast to the non-robust case (i.e., without uncertainties) they no longer provide optimal solutions for the robust problem, but rather yield a worst case optimality gap of at least T. We finally show that for infinite delays, the optimality gap is at most O(k log T), where k is a newly introduced instance characteristic. The results obtained in this paper yield a first step towards understanding robust dynamic flow problems with uncertain travel times.