Refine
Document Type
- ZIB-Report (21)
Language
- English (21)
Has Fulltext
- yes (21) (remove)
Is part of the Bibliography
- no (21)
Keywords
Institute
- Mathematical Optimization (19)
- ZIB Allgemein (2)
A model for the optimisation of the location and configuration of base stations in a UMTS network is described. The focus is primarily on modelling the configuration problem sufficiently accurate using mixed-integer variables and (essentially) linear constraints. These constraints reflect the limited downlink code capacity in each cell, the interference limitations for successful up- and downlink transmissions, the need for sufficiently strong (cell) pilot signals, and the potential gain for mobiles from being in soft(er) hand-over. It is also explained how to use the model as a basis for rating network configurations.
The UMTS radio network planning problem poses the challenge of designing a cost-effective network that provides users with sufficient coverage and capacity. We describe an optimization model for this problem that is based on comprehensive planning data of the EU project MOMENTUM. We present heuristic mathematical methods for this realistic model, including computational results.
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.
In this paper, we study self-avoiding walks of a given length on a graph. We consider a formulation of this problem as a binary linear program. We analyze the polyhedral structure of the underlying polytope and describe valid inequalities. Proofs for their facial properties for certain special cases are given. In a variation of this problem one is interested in optimal configurations, where an energy function measures the benefit if certain path elements are placed on adjacent vertices of the graph. The most prominent application of this problem is the protein folding problem in biochemistry. On a set of selected instances, we demonstrate the computational merits of our approach.
We consider a nonlinear nonconvex network flow problem that arises, for example, in natural gas or water transmission networks. Given is such network with active and passive components, that is, valves, compressors, pressure regulators (active) and pipelines (passive), and a desired amount of flow at certain specified entry and exit nodes of the network. Besides flow conservation constraints in the nodes the flow must fulfill nonlinear nonconvex pressure loss constraints on the arcs subject to potential values (i.e., pressure levels) in both end nodes of each arc. The problem is how to numerically compute this flow and pressures. We review an existing approach of Maugis (1977) and extend it to the case of networks with active elements (for example, compressors). We further examine different ways of relaxations for the nonlinear network flow model. We compare different approaches based on nonlinear optimization numerically on a set of test instances.
Identification of trade-offs for sustainable manufacturing of a Bamboo Bike by System Dynamics
(2013)
We develop a generic System Dynamic model to simulate the production, machines, employees, waste, and capital flows of a manufacturing company. In a second step, this model is specialised by defining suit-able input data to represent a bicycle manufacturing company in a developing country. We monitor a set of sustainability indicators to understand the social, environmental and economic impact of the company, and to estimate managerial decisions to be taken in order to improve on these criteria. We show that the social and environmental situation can be improved over time without sacrificing the economic success of the company's business.
We consider the following freight train routing problem (FTRP). Given is a
transportation network with fixed routes for passenger trains and a
set of freight trains (requests), each defined by an origin and
destination station pair. The objective is to calculate a feasible
route for each freight train such that a sum of all expected delays and
all running times is minimal. Previous research concentrated on
microscopic train routings for junctions or inside major stations. Only
recently approaches were developed to tackle larger corridors or even
networks. We investigate the routing problem from a strategic
perspective, calculating the routes in a macroscopic transportation
network of Deutsche Bahn AG. Here macroscopic refers to an aggregation of
complex real-world structures are into fewer network elements. Moreover, the
departure and arrival times of freight trains are approximated.
The problem has a strategic
character since it asks only for a coarse routing through the network
without the precise timings. We give a mixed-integer nonlinear programming~(MINLP)
formulation for FTRP, which is a multi-commodity flow model on a time-expanded
graph with additional routing constraints. The model's nonlinearities are due to
an algebraic approximation of the delays of the trains on the arcs of
the network
by capacity restraint functions. The MINLP is reduced to a mixed-integer linear model~(MILP)
by piecewise linear approximation. The latter is solved by a state of the art MILP solver for various real-world test instances.
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.
We consider a nonlinear nonconvex network design problem that arises in the extension of natural gas transmission networks. Given is such network with active and passive components, that is, valves, compressors, pressure regulators (active) and pipelines (passive), and a desired amount of flow at certain specified entry and exit nodes of the network. Besides flow conservation constraints in the nodes the flow must fulfill nonlinear nonconvex pressure loss constraints on the arcs subject to potential values (i.e., pressure levels) in both end nodes of each arc. Assume that there does not exist a feasible flow that fulfills all physical constraints and meets the desired entry and exit amounts. Then a natural question is where to extend the network by adding pipes in the most economic way such that this flow becomes feasible. Answering this question is computationally demanding because of the difficult problem structure. We use mixed-integer nonlinear programming techniques that rely on an outer approximation of the overall problem, and a branching on decision variables. We formulate a new class of valid inequalities (or cutting planes) which reduce the overall solution time when added to the formulation. We demonstrate the computational merits of our approach on test instances.
We study System Dynamics models with several free parameters that can be altered by the user. We assume that the user's goal is to achieve a certain dynamic behavior of the model by varying these parameters. In order to the find best possible combination of parameter settings, several automatic parameter tuning methods are described in the literature and readily available within existing System Dynamic software packages. We give a survey on the available techniques in the market and describe their theoretical background. Some of these methods are already six decades old, and meanwhile newer and more powerful optimization methods have emerged in the mathematical literature. One major obstacle for their direct use are tabled data in System Dynamics models, which are usually interpreted as piecewise linear functions. However, modern optimization methods usually require smooth functions which are twice continuously differentiable. We overcome this problem by a smooth spline interpolation of the tabled data. We use a test set of three complex System Dynamic models from the literature, describe their individual transition into optimization problems, and demonstrate the applicability of modern optimization algorithms to these System Dynamics Optimization problems.
The System Dynamics (SD) methodology is a framework for modeling and simulating
the dynamic behavior of socioeconomic systems. Characteristic for the
description of such systems is the occurrence of feedback loops together with
stocks and flows. The mathematical equations that describe the system are
usually nonlinear. Therefore seemingly simple systems can show a nonintuitive,
nonpredictable behavior over time. Controlling a dynamical system means to
define a desired final state in which the system should be, and to specify
potential interventions from outside that should keep the system on the right
track. The central question is how to compute such globally optimal control for
a given SD model. We propose a branch-and-bound approach that is based on a
bound propagation method, primal heuristics, and spatial branching. We apply our
new SD-control method to a small System Dynamics model, that describes the
evolution of a social-economic system over time. We examine the problem of
steering this system on a sustainable consumption path.
The Scenario Technique is a strategic planning method that aims to describe and analyze potential developments of a considered system in the future. Its application consists of several steps, from an initial problem analysis over an influence analysis to projections of key factors and a definition of the scenarios to a final interpretation of the results. The technique itself combines qualitative and quantitative methods and is an enhancement of the standard Scenario Technique. We use the numerical values gathered during the influence analysis, and embed them in a System Dynamics framework. This yields a mathematically rigorous way to achieve predictions of the system‘s future behavior from an initial impulse and the feedback structure of the factors. The outcome of our new method is a further way of projecting the present into the future, which enables the user of the Scenario Technique to obtain a validation of the results achieved by the standard method.
We consider a production planning problem where two competing companies are selling their items on a common market. Moreover, the raw material used in the production is a limited non-renewable resource. The revenue per item sold depends on the total amount of items produced by both players. If they collaborate they could apply a production strategy that leads to the highest combined revenue. Usually the formation of such syndicates is prohibited by law; hence we assume that one company does not know how much the other company will produce. We formulate the problem for company A to find an optimal production plan without information on the strategy of company B as a nonlinear mathematical optimization problem. In its naive formulation the model is too large, making its solution practically impossible. After a reformulation we find a much smaller model, which we solve by spatial branch-and-cut methods and linear programming. We discuss the practical implications of our solutions.
The System Dynamics (SD) methodology is a framework for modeling and simulating the dynamic behavior of socioeconomic systems. Characteristic for the description of such systems is the occurrence of feedback loops together with stocks and flows. The mathematical equations that describe the system are usually ordinary differential equations and nonlinear algebraic constraints. Therefore seemingly simple systems can show a nonintuitive, unpredictable behavior over time. Controlling a dynamical system means to specify potential interventions from outside that should keep the system on the desired track, and to define an evaluation schema to compare different controls among each other, so that a "best" control can be defined in a meaningful way. The central question is how to compute such globally optimal control for a given SD model, that allows the transition of the system into a desired state with minimum effort. We propose a mixed-integer nonlinear programming (MINLP) reformulation of the System Dynamics Optimization (SDO) problem. MINLP problems can be solved by linear programming based branch-and-bound approach. We demonstrate that standard MINLP solvers are not able to solve SDO problem. To overcome this obstacle, we introduce a special-tailored bound propagation method. We apply our new method to a predator-prey model with additional hunting activity as control, and to a mini-world model with the consumption level as control. Numerical results for these test cases are presented.
We present a novel heuristic algorithm to identify feasible solutions of a mixed-integer nonlinear programming problem arising in natural gas transportation: the selection of new pipelines to enhance the network's capacity to a desired level in a cost-efficient way. We solve this problem in a linear programming based branch-and-cut approach, where we deal with the nonlinearities by linear outer approximation and spatial branching. At certain nodes of the branching tree, we compute a KKT point for a nonlinear relaxation. Based on the information from the KKT point we alter some of the integer variables in a locally promising way. We describe this heuristic for general MINLPs and then show how to tailor the heuristic to exploit our problem-specific structure. On a test set of real-world instances, we are able to increase the chance of identifying feasible solutions by some order of magnitude compared to standard MINLP heuristics that are already built in the general-purpose MINLP solver SCIP.
We consider problems concerning the scheduling of a set of trains on a single track. For every pair of trains there is a minimum headway, which every train must wait before it enters the track after another train. The speed of each train is also given. Hence for every schedule - a sequence of trains - we may compute the time that is at least needed for all trains to travel along the track in the given order. We give the solution to three problems: the fastest schedule, the average schedule, and the problem of quantile schedules. The last problem is a question about the smallest upper bound on the time of a given fraction of all possible schedules. We show how these problems are related to the travelling salesman problem. We prove NP-completeness of the fastest schedule problem, NP-hardness of quantile of schedules problem, and polynomiality of the average schedule problem. We also describe some algorithms for all three problems. In the solution of the quantile problem we give an algorithm, based on a reverse search method, generating with polynomial delay all Eulerian multigraphs with the given degree sequence and a bound on the number of such multigraphs. A better bound is left as an open question.
In this article we investigate methods to solve a fundamental task in gas transportation, namely the validation of nomination problem: Given a gas transmission network consisting of passive pipelines and active, controllable elements and given an amount of gas at every entry and exit point of the network, find operational settings for all active elements such that there exists a network state meeting all physical, technical, and legal constraints.
We describe a two-stage approach to solve the resulting complex and numerically difficult mixed-integer non-convex nonlinear feasibility problem. The first phase consists of four distinct algorithms facilitating mixed-integer linear, mixed-integer nonlinear, reduced nonlinear, and complementarity constrained methods to compute possible settings for the discrete decisions. The second phase employs a precise continuous nonlinear programming model of the gas network. Using this setup, we are able to compute high quality solutions to real-world industrial instances whose size is significantly larger than networks that have appeared in the literature previously.
The industrial treatment of waste paper in order to regain valuable
fibers from which recovered paper can be produced, involves several
steps of preparation. One important step is the separation of stickies
that are normally attached to the paper. If not properly separated,
remaining stickies reduce the quality of the recovered paper or even
disrupt the production process. For the mechanical separation process
of fibers from stickies a separator screen is used. This machine has
one input feed and two output streams, called the accept and the
reject. In the accept the fibers are concentrated, whereas the reject
has a higher concentration of stickies. The machine can be controlled
by setting its reject rate. But even when the reject rate is set
properly, after just a single screening step, the accept still has too
many stickies, or the reject too many fibers. To get a proper
separation, several separators have to be assembled into a
network. From a mathematical point of view this problem can be seen as
a multi-commodity network flow design problem with a nonlinear,
controllable distribution function at each node. We present a
nonlinear mixed-integer programming model for the simultaneous
selection of a subset of separators, the network's topology, and the
optimal setting of each separator.
Numerical results are obtained via
different types of linearization of the nonlinearities and the use of
mixed-integer linear solvers, and compared with state-of-the-art
global optimization software.
It is clear that a transformation to sustainable value creation is needed, because business as usual is not an option for preserving competitive advantages of leading industries. What does that mean? This contribution proposes possible approaches for a shift in existing manufacturing paradigms. In a first step, sustainability aspects from the German Sustainability Strategy and from the tools of life cycle sustainability assessment are chosen to match areas of a value creation process. Within these aspects are indicators, which can be measured within a manufacturing process. Once these data are obtained they can be used to set up a mathematical linear pulse model of manufacturing in order to analyse the evolution of the system over time, that is the transition process, by using a system dynamics approach. An increase of technology development by a factor of 2 leads to an increase of manufacturing but also to an increase of climate change. Compensation measures need to be taken. This can be done by e.g. taking money from the GDP (as an indicator of the aspect ``macroeconomic performance''). The value of the arc from that building block towards climate change must then be increased by a factor of 10. The choice of independent and representative indicators or aspects shall be validated and double-checked for their significance with the help of multi-criteria mixed-integer programming optimisation methods.