90B10 Network models, deterministic
Refine
Document Type
- ZIB-Report (6)
Language
- English (6)
Has Fulltext
- yes (6)
Is part of the Bibliography
- no (6)
Keywords
Institute
The recently imposed new gas market liberalization rules in Germany lead to a change of business of gas network operators.
While previously network operator and gas vendor where united, they were forced to split up into independent companies.
The network has to be open to any other gas trader at the same conditions, and free network capacities have to be identified and publicly offered in a non-discriminatory way.
We show that these new paradigms lead to new and challenging mathematical optimization problems.
In order to solve them and to provide meaningful results for practice, all aspects of the underlying problems, such as combinatorics, stochasticity, uncertainty, and nonlinearity, have to be addressed.
With such special-tailored solvers, free network capacities and topological network extensions can, for instance, be determined.
Gas distribution networks are complex structures that consist of
passive pipes, and active, controllable elements such as valves and
compressors. Controlling such network means to find a suitable setting
for all active components such that a nominated amount of gas can be
transmitted from entries to exits through the network, without
violating physical or operational constraints. The control of a
large-scale gas network is a challenging task from a practical point
of view. In most companies the actual controlling process is supported
by means of computer software that is able to simulate the flow of the
gas. However, the active settings have to be set manually within such
simulation software. The solution quality thus depends on the
experience of a human planner.
When the gas network is insufficient for the transport then topology
extensions come into play. Here a set of new pipes or active elements
is determined such that the extended network admits a feasible control
again. The question again is how to select these extensions and where
to place them such that the total extension costs are
minimal. Industrial practice is again to use the same simulation
software, determine extensions by experience, add them to the virtual
network, and then try to find a feasible control of the active
elements. The validity of this approach now depends even more on the
human planner.
Another weakness of this manual simulation-based approach is that it
cannot establish infeasibility of a certain gas nomination, unless all
settings of the active elements are tried. Moreover, it is impossible
to find a cost-optimal network extension in this way.
In order to overcome these shortcomings of the manual planning
approach we present a new approach, rigorously based on mathematical
optimization. Hereto we describe a model for finding feasible
controls and then extend this model such that topology extensions can
additionally and simultaneously be covered. Numerical results for real-world instances are presented and
discussed.
The Coolest Path Problem
(2009)
We introduce the coolest path problem, which is a mixture of two well-known problems from distinct mathematical fields. One of them is the shortest path problem from combinatorial optimization. The other is the heat conduction problem from the field of partial differential equations. Together, they make up a control problem, where some geometrical object traverses a digraph in an optimal way, with constraints on intermediate or the final state. We discuss some properties of the problem and present numerical solution techniques. We demonstrate that the problem can be formulated as a linear mixed-integer program. Numerical solutions can thus be achieved within one hour for instances with up to 70 nodes in the graph.
The topic of this paper is minimum cost operative planning of pressurized water supply networks over a finite horizon and under reliable demand forecast. Since this is a very hard problem, it is desirable to employ sophisticated mathematical algorithms, which in turn calls for carefully designed models with suitable properties. The paper develops a nonlinear mixed integer model and a nonlinear programming model with favorable properties for gradient-based optimization methods, based on smooth component models for the network elements. In combination with further nonlinear programming techniques (to be reported elsewhere), practically satisfactory near-optimum solutions even for large networks can be generated in acceptable time using standard optimization software on a PC workstation. Such an optimization system is in operation at Berliner Wasserbetriebe.
In this article, strategical infrastructure planning problems in the design of large-scale telecommunication networks are discussed based on experiences from three projects with industrial partners: The access network planning of the German Gigabit-Wissenschaftsnetz (G-WiN) for DFN (Verein zur Förderung eines Deutschen Forschungsnetzes e.V.), the mobile network switching center location planning project for E-Plus Mobilfunk, and the fixed network switching center location planning project for TELEKOM AUSTRIA. We introduce a mathematical model for a hierarchical multi-commodity capacitated facility location problem, present adaptions of this basic model to the specific requirements within the different projects and discuss the individual peculiarities and model decisions made. Eventually, we present and discuss computational results of three associated case studies, illustrating '"how we did the job`` with mathematical methods.
Mobile telecommunication systems establish a large number of communication links with a limited number of available frequencies; reuse of the same or adjacent frequencies on neighboring links causes interference. The task to find an assignment of frequencies to channels with minimal interference is the frequency assignment problem. The frequency assignment problem is usually treated as a graph coloring problem where the number of colors is minimized, but this approach does not model interference minimization correctly. We give in this paper a new integer programming formulation of the frequency assignment problem, the orientation model, and develop a heuristic two-stage method to solve it. The algorithm iteratively solves an outer and an inner optimization problem. The outer problem decides for each pair of communication links which link gets the higher frequency and leads to an acyclic subdigraph problem with additional longest path restrictions. The inner problem to find an optimal assignment respecting an orientation leads to a min-cost flow problem.