Refine
Year of publication
- 2013 (6) (remove)
Document Type
- ZIB-Report (3)
- Article (1)
- Book chapter (1)
- In Collection (1)
Language
- English (6)
Is part of the Bibliography
- no (6)
Keywords
Institute
Presolving attempts to eliminate redundant information from the problem formulation and simultaneously tries to strengthen the formulation. It can be very effective and is often essential for solving instances. Especially for mixed integer programming problems, fast and effective presolving algorithms are very important. In this paper, we report on three new presolving techniques. The first method searches for singleton continuous columns and tries to fix the corresponding variables. Then we present a presolving technique which exploits a partial order of the variables to induce fixings. Finally, we show an approach based on connected components in graphs. Our computational results confirm the profitable use of the algorithms in practice.
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 were 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 discuss how these changing paradigms lead to new and challenging mathematical optimization problems. This includes the validation of nominations, that asks for the decision if the network’s capacity is sufficient to transport a specific amount of flow, the verification of booked capacities and the detection of available freely allocable capacities, and the topological extension of the network with new pipelines or compressors in order to increase its capacity. In order to solve each of these problems and to provide meaningful results for the practice, a mixture of different mathematical aspects have to be addressed, such as combinatorics, stochasticity, uncertainty, and nonlinearity. Currently, no numerical solver is available that can deal with such blended problems out-of-the-box. The main goal of our research is to develop such a solver, that moreover is able to solve instances of realistic size. In this article, we describe the main ingredients of our prototypical software implementations.
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.
Steiner trees are constructed to connect a set of terminal nodes in a graph. This basic version of the Steiner tree problem is idealized, but it can effectively guide the search for successful approaches to many relevant variants, from both a theoretical and a computational point of view. This article illustrates the theoretical and algorithmic progress on Steiner tree type problems on two examples, the Steiner connectivity and the Steiner tree packing problem.