@article{SchweigerLiers, author = {Schweiger, Jonas and Liers, Frauke}, title = {A Decomposition Approach for Optimal Gas Network Extension with a Finite Set of Demand Scenarios}, series = {Optimization and Engineering}, volume = {19}, journal = {Optimization and Engineering}, number = {2}, publisher = {Springer}, pages = {297 -- 326}, abstract = {Today's gas markets demand more flexibility from the network operators which in turn have to invest into their network infrastructure. As these investments are very cost-intensive and long-living, network extensions should not only focus on a single bottleneck scenario, but should increase the flexibility to fulfill different demand scenarios. In this work, we formulate a model for the network extension problem for multiple demand scenarios and propose a scenario decomposition in order to solve the arising challenging optimization tasks. In fact, each subproblem consists of a mixed-integer nonlinear optimization problem (MINLP). Valid bounds on the objective value are derived even without solving the subproblems to optimality. Furthermore, we develop heuristics that prove capable of improving the initial solutions substantially. Results of computational experiments on realistic network topologies are presented. It turns out that our method is able to solve these challenging instances to optimality within a reasonable amount of time.}, language = {en} } @misc{HillerKochScheweetal., author = {Hiller, Benjamin and Koch, Thorsten and Schewe, Lars and Schwarz, Robert and Schweiger, Jonas}, title = {A System to Evaluate Gas Network Capacities: Concepts and Implementation}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-67438}, abstract = {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.}, language = {en} } @article{HillerKochScheweetal., author = {Hiller, Benjamin and Koch, Thorsten and Schewe, Lars and Schwarz, Robert and Schweiger, Jonas}, title = {A System to Evaluate Gas Network Capacities: Concepts and Implementation}, series = {European Journal of Operational Research}, volume = {270}, journal = {European Journal of Operational Research}, number = {3}, pages = {797 -- 808}, abstract = {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 trans- ported 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.}, language = {en} } @misc{HillerKochScheweetal., author = {Hiller, Benjamin and Koch, Thorsten and Schewe, Lars and Schwarz, Robert and Schweiger, Jonas}, title = {A System to Evaluate Gas Network Capacities: Concepts and Implementation}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61931}, abstract = {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.}, language = {en} } @inproceedings{EisenblaetterGeerdesGrossetal.2010, author = {Eisenbl{\"a}tter, Andreas and Geerdes, Hans-Florian and Gross, James and Pu{\~n}al, Oscar and Schweiger, Jonas}, title = {A Two-Stage Approach to WLAN Planning}, series = {Proc. of the 8th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt'10)}, booktitle = {Proc. of the 8th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt'10)}, address = {Avignon, France}, pages = {232 -- 241}, year = {2010}, language = {en} } @misc{Schweiger, type = {Master Thesis}, author = {Schweiger, Jonas}, title = {Application of Multistage Stochastic Programming in Strategic Telecommunication Network Planning}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12206}, school = {Zuse Institute Berlin (ZIB)}, pages = {149}, abstract = {Telecommunication is fundamental for the information society. In both, the private and the professional sector, mobile communication is nowadays taken for granted. Starting primarily as a service for speech communication, data service and mobile Internet access are now driving the evolution of network infrastructure. In the year 2009, 19 million users generated over 33 million GB of traffic using mobile data services. The 3rd generation networks (3G or UMTS) in Germany comprises over 39,000 base stations with some 120,000 cells. From 1998 to 2008, the four network operators in Germany invested over 33 billion Euros in their infrastructure. A careful allocation of the resources is thus crucial for the profitability for a network operator: a network should be dimensioned to match customers demand. As this demand evolves over time, the infrastructure has to evolve accordingly. The demand evolution is hard to predict and thus constitutes a strong source of uncertainty. Strategic network planning has to take this uncertainty into account, and the planned network evolution should adapt to changing market conditions. The application of superior planning methods under the consideration of uncertainty can improve the profitability of the network and creates a competitive advantage. Multistage stochastic programming is a suitable framework to model strategic telecommunication network planning. We present mathematical models and effective optimization procedures for strategic cellular network design. The demand evolution is modeled as a continuous stochastic process which is approximated by a discrete scenario tree. A tree-stage approach is used for the construction of non-uniform scenario trees that serve as input of the stochastic program. The model is calibrated by historical traffic observations. A realistic system model of UMTS radio cells is used that determines coverage areas and cell capacities and takes signal propagation and interferences into account. The network design problem is formulated as a multistage stochastic mixed integer linear program, which is solved using state-of-the-art commercial MIP solvers. Problem specific presolving is proposed to reduce the problem size. Computational results on realistic data is presented. Optimization for the expected profit and the conditional value at risk are performed and compared.}, language = {en} } @incollection{HillerHumpolaLehmannetal., author = {Hiller, Benjamin and Humpola, Jesco and Lehmann, Thomas and Lenz, Ralf and Morsi, Antonio and Pfetsch, Marc and Schewe, Lars and Schmidt, Martin and Schwarz, Robert and Schweiger, Jonas and Stangl, Claudia and Willert, Bernhard}, title = {Computational results for validation of nominations}, series = {Evaluating Gas Network Capacities}, volume = {SIAM-MOS series on Optimization}, booktitle = {Evaluating Gas Network Capacities}, isbn = {9781611973686}, abstract = {The different approaches to solve the validation of nomination problem presented in the previous chapters are evaluated computationally in this chapter. Each approach is analyzed individually, as well as the complete solvers for these problems. We demonstrate that the presented approaches can successfully solve large-scale real-world instances.}, language = {en} } @misc{Schweiger, author = {Schweiger, Jonas}, title = {Exploiting structure in non-convex quadratic optimization}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69476}, abstract = {The amazing success of computational mathematical optimization over the last decades has been driven more by insights into mathematical structures than by the advance of computing technology. In this vein, we address applications, where nonconvexity in the model poses principal difficulties. This paper summarizes the dissertation of Jonas Schweiger for the occasion of the GOR dissertation award 2018. We focus on the work on non-convex quadratic programs and show how problem specific structure can be used to obtain tight relaxations and speed up Branch\&Bound methods. Both a classic general QP and the Pooling Problem as an important practical application serve as showcases.}, language = {en} } @phdthesis{Schweiger, author = {Schweiger, Jonas}, title = {Exploiting structure in non-convex quadratic optimization and gas network planning under uncertainty}, pages = {411}, abstract = {The amazing success of computational mathematical optimization over the last decades has been driven more by insights into mathematical structures than by the advance of computing technology. In this vein, we address applications, where nonconvexity in the model and uncertainty in the data pose principal difficulties. The first part of the thesis deals with non-convex quadratic programs. Branch\&Bound methods for this problem class depend on tight relaxations. We contribute in several ways: First, we establish a new way to handle missing linearization variables in the well-known Reformulation-Linearization-Technique (RLT). This is implemented into the commercial software CPLEX. Second, we study the optimization of a quadratic objective over the standard simplex or a knapsack constraint. These basic structures appear as part of many complex models. Exploiting connections to the maximum clique problem and RLT, we derive new valid inequalities. Using exact and heuristic separation methods, we demonstrate the impact of the new inequalities on the relaxation and the global optimization of these problems. Third, we strengthen the state-of-the-art relaxation for the pooling problem, a well-known non-convex quadratic problem, which is, for example, relevant in the petrochemical industry. We propose a novel relaxation that captures the essential non-convex structure of the problem but is small enough for an in-depth study. We provide a complete inner description in terms of the extreme points as well as an outer description in terms of inequalities defining its convex hull (which is not a polyhedron). We show that the resulting valid convex inequalities significantly strengthen the standard relaxation of the pooling problem. The second part of this thesis focuses on a common challenge in real world applications, namely, the uncertainty entailed in the input data. We study the extension of a gas transport network, e.g., from our project partner Open Grid Europe GmbH. For a single scenario this maps to a challenging non-convex MINLP. As the future transport patterns are highly uncertain, we propose a robust model to best prepare the network operator for an array of scenarios. We develop a custom decomposition approach that makes use of the hierarchical structure of network extensions and the loose coupling between the scenarios. The algorithm used the single-scenario problem as black-box subproblem allowing the generalization of our approach to problems with the same structure. The scenario-expanded version of this problem is out of reach for today's general-purpose MINLP solvers. Yet our approach provides primal and dual bounds for instances with up to 256 scenarios and solves many of them to optimality. Extensive computational studies show the impact of our work.}, language = {en} } @misc{Schweiger, author = {Schweiger, Jonas}, title = {Gas network extension planning for multiple demand scenarios}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-51030}, abstract = {Today's gas markets demand more flexibility from the network operators which in turn have to invest into their network infrastructure. As these investments are very cost-intensive and long-living, network extensions should not only focus on one bottleneck scenario, but should increase the flexibility to fulfill different demand scenarios. We formulate a model for the network extension problem for multiple demand scenarios and propose a scenario decomposition. We solve MINLP single-scenario sub-problems and obtain valid bounds even without solving them to optimality. Heuristics prove capable of improving the initial solutions substantially. Results of computational experiments are presented.}, language = {en} }