Refine
Document Type
- ZIB-Report (12) (remove)
Has Fulltext
- yes (12)
Is part of the Bibliography
- no (12)
Keywords
- Buchungsvalidierung (1)
- Entry-Exit Model (1)
- Expansion Planning (1)
- Gas Distribution Networks (1)
- Gas Market Liberalization (1)
- Gas Network Access Regulation (1)
- Gas Network Applications (1)
- Gasnetzplanung (1)
- LP solver (1)
- MINLP solver (1)
- MIP solver (1)
- Mathematical Optimization (1)
- Mixed Integer Nonlinear Programming (1)
- Mixed-Integer Nonlinear Nonconvex Stochastic Optimization (1)
- Nominierungsvalidierung (1)
- SCIP, Mathematical optimization, Python, Modeling (1)
- Steiner tree solver (1)
- Technische Kapazitäten (1)
- Topologieplanung (1)
- Topology Planning (1)
- bilevel optimization (1)
- branch-cut-and-price framework (1)
- entry-exit model (1)
- freely allocable capacity (1)
- gas network optimization (1)
- gas networks (1)
- generic column generation (1)
- large-scale mixed-integer nonlinear programming (1)
- linear programming (1)
- mixed-integer linear and nonlinear programming (1)
- mixed-integer semidefinite programming (1)
- modeling (1)
- multi-criteria optimization (1)
- network flow (1)
- operations research in energy (1)
- parallel branch-and-bound (1)
- simplex method (1)
Institute
Recently, Kronqvist et al. (2016) rediscovered the supporting hyperplane algorithm of Veinott (1967) and demonstrated its computational benefits for solving convex mixed-integer nonlinear programs. In this paper we derive the algorithm from a geometric point of view. This enables us to show that the supporting hyperplane algorithm is equivalent to Kelley's cutting plane algorithm applied to a particular reformulation of the problem. As a result, we extend the applicability of the supporting hyperplane algorithm to convex problems represented by general, not necessarily convex, differentiable functions that satisfy a mild condition.
In 2005 the European Union liberalized the gas market with a disruptive change and decoupled trading of natural gas from its transport. The gas is now transported by independent so-called transmissions system operators or TSOs. The market model established by the European Union views the gas transmission network as a black box, providing shippers (gas traders and consumers) the opportunity to transport gas from any entry to any exit. TSOs are required to offer the maximum possible capacities at each entry and exit such that any resulting gas flow can be realized by the network. The revenue from selling these capacities more than one billion Euro in Germany alone, but overestimating the capacity might compromise the security of supply. Therefore, evaluating the available transport capacities is extremely important to the TSOs.
This is a report on a large project in mathematical optimization, set out to develop a new toolset for evaluating gas network capacities. The goals and the challenges as they occurred in the project are described, as well as the developments and design decisions taken to meet the requirements.
Since 2005, the gas market in the European Union is liberalized and the trading of natural gas is decoupled from its transport. The transport is done by so-called transmissions system operators or TSOs. The market model established by the European Union views the gas transmission network as a black box, providing shippers (gas traders and consumers) the opportunity to transport gas from any entry to any exit. TSOs are required to offer maximum independent capacities at each entry and exit such that the resulting gas flows can be realized by the network without compromising security of supply. Therefore, evaluating the available transport capacities is extremely important to the TSOs.
This paper gives an overview of the toolset for evaluating gas network capacities that has been developed within the ForNe project, a joint research project of seven research partners initiated by Open Grid Europe, Germany's biggest TSO. While most of the relevant mathematics is described in the book "Evaluating Gas Network Capacities", this article sketches the system as a whole, describes some developments that have taken place recently, and gives some details about the current implementation.
The SCIP Optimization Suite is a powerful collection of optimization software that consists of the branch-cut-and-price framework and mixed-integer programming solver SCIP, the linear programming solver SoPlex, the modeling language Zimpl, the parallelization framework UG, and the generic branch-cut-and-price solver GCG. Additionally, it features the extensions SCIP-Jack for solving Steiner tree problems, PolySCIP for solving multi-objective problems, and SCIP-SDP for solving mixed-integer semidefinite programs. The SCIP Optimization Suite has been continuously developed and has now reached version 4.0. The goal of this report is to present the recent changes to the collection. We not only describe the theoretical basis, but focus on implementation aspects and their computational consequences.
In the context of gas transmission in decoupled entry-exit systems, many approaches to determine the network capacity are based on the evaluation of realistic and severe transport situations. In this paper, we review the Reference Point Method, which is an algorithm used in practice to generate a set of scenarios using the so-called transport moment as a measure for severity. We introduce a new algorithm for finding severe transport situations that considers an actual routing of the flow through the network and is designed to handle issues arising from cyclic structures in a more dynamical manner. Further, in order to better approximate the physics of gas, an alternative, potential based flow formulation is proposed. The report concludes with a case study based on data from the benchmark library GasLib.
In this paper, we compare several approaches for the problem of gas network expansions using loops, that is, to build new pipelines in parallel to existing ones. We present different model formulations for the problem of continuous loop expansions as well as discrete loop expansions. We then analyze problem properties, such as the structure and convexity of the underlying feasible regions. The paper concludes with a computational study comparing the continuous and the discrete formulations.
SCIP is a solver for a wide variety of mathematical optimization problems. It is written in C and extendable due to its plug-in based design. However, dealing with all C specifics when extending SCIP can be detrimental to development and testing of new ideas. This paper attempts to provide a remedy by introducing PySCIPOpt, a Python interface to SCIP that enables users to write new SCIP code entirely in Python. We demonstrate how to intuitively model mixed-integer linear and quadratic optimization problems and moreover provide examples on how new Python plug-ins can be added to SCIP.
The SCIP Optimization Suite is a software toolbox for generating and solving various classes of mathematical optimization problems. Its major components are the modeling language ZIMPL, the linear programming solver SoPlex, the constraint integer programming framework and mixed-integer linear and nonlinear programming solver SCIP, the UG framework for parallelization of branch-and-bound-based solvers, and the generic branch-cut-and-price solver GCG. It has been used in many applications from both academia and industry and is one of the leading non-commercial solvers.
This paper highlights the new features of version 3.2 of the SCIP Optimization Suite. Version 3.2 was released in July 2015. This release comes with new presolving steps, primal heuristics, and branching rules within SCIP. In addition, version 3.2 includes a reoptimization feature and improved handling of quadratic constraints and special ordered sets. SoPlex can now solve LPs exactly over the rational number and performance improvements have been achieved by exploiting sparsity in more situations. UG has been tested successfully on 80,000 cores. A major new feature of UG is the functionality to parallelize a customized SCIP solver. GCG has been enhanced with a new separator, new primal heuristics, and improved column management. Finally, new and improved extensions of SCIP are presented, namely solvers for multi-criteria optimization, Steiner tree problems, and mixed-integer semidefinite programs.
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.
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.