Refine
Year of publication
Document Type
- In Proceedings (38)
- Article (31)
- ZIB-Report (21)
- Book chapter (5)
- Other (4)
- Book (2)
- Habilitation (1)
- Master's Thesis (1)
Language
- English (103)
Is part of the Bibliography
- no (103)
Keywords
Institute
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.
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.
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.
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.
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.