Matheon Project B20 – Optimization of Gas Transport

Contact: Thorsten Koch, ZIB Institutions: Konrad-Zuse-Zentrum für Informationstechnik Berlin Humboldt-Universität zu Berlin Weierstraß-Institut für Angewandte Analysis und Stochastik Project Heads: Martin Grötschel, ZIB René Henrion, WIAS Thorsten Koch, ZIB Werner Römisch, HU Berlin Members: Timo Berthold, ZIB Stefan Heinz, ZIB Stefan Vigerske, HU Berlin Associated: Tobias Achterberg Armin Fügenschuh, ZIB Ambros Gleixner, ZIB Kati Wolter, ZIB Duration: 05/2009–05/2010 Funding: DFG Forschungszentrum Matheon "Mathematics for key technologies: Modelling, simulation, and optimization of real-world processes"

Project Description

Natural gas is one of the most important energy sources in Germany and Europe. In recent years, political regulations have led to a strict separation of gas trading and gas transport, thereby assigning a central role in energy politics to the transportation and distribution of gas. These newly imposed political requirements influenced the technical processes of gas transport in such a way that the complex task of planning and operating gas networks has still intensified.

Mathematically, the combination of discrete decisions on the configuration of a gas transport network (a), the nonlinear equations describing the physics of gas (b), the newly imposed deregulation rules (c), and the uncertainty in demand and supply (d) yield large-scale and highly complex stochastic mixed-integer nonlinear constraint programs. For solving this type of problems, no suitable algorithms or software are available by now. With respect to each individual aspects of stochastic mixed-integer nonlinear constraint programming, i.e., mixed-integer linear programming, global optimization of nonlinear programs, constraint satisfaction, and stochastic programming, remarkable progress has been made, however, over the last decades. The goal of this project is to incorporate these powerful technologies into a general framework which can solve the mixed-integer nonlinear constraint programs with stochastic components arising in gas transport and other applications.

(a) Network configuration	(b) Physics of gas	(c) Legal requirements	(d) Uncertain demand
Mixed-Integer Programming	Nonlinear Programming	Constraint Programming	Stochastic Programming

Poster

• Poster (12/2009) [pdf]
• Poster (12/2009) [ps.gz]

Publications

• Michael Bussieck and Stefan Vigerske. MINLP Solver Software submitted.
• Winfried Neun and Thomas Sturm and Stefan Vigerske. Supporting Global Numerical Optimization of Rational Functions by Generic Symbolic Convexity Tests ZIB-Report 10-01.
• Timo Berthold and Ambros Gleixner. Undercover - a primal heuristic for MINLP based on sub-MIPs generated by set covering ZIB-Report 09-40.
• Andreas Bley, Ambros Gleixner, Thorsten Koch, and Stefan Vigerske. Comparing MIQCP solvers to a specialised algorithm for mine production scheduling ZIB-Report 09-32 and Matheon Preprint 671.
• Timo Berthold, Stefan Heinz, and Stefan Vigerske. Extending a CIP framework to solve MIQCPs. ZIB-Report 09-23 and Matheon Preprint 596.
• Timo Berthold, Stefan Heinz, and Marc E. Pfetsch. Nonlinear pseudo-Boolean optimization: relaxation or propagation? Proc. of SAT 2009, pp. 441–446, 2009. Former ZIB-Report 09-11.
• Tobias Achterberg, and Timo Berthold. Hybrid Branching. Proc. of CPAIOR 2009, pp. 309–311, 2009. Former Matheon Preprint 597.
• Tobias Achterberg. SCIP: Solving Constraint Integer Programs. Mathematical Programming Computation Nr. 1(1), pp. 1–41, 2009.
• Tobias Achterberg, Timo Berthold, Stefan Heinz, Thorsten Koch, and Kati Wolter. Constraint Integer Programming: Techniques and Applications. ZIB-Report 08-43, submitted, 2008.

Partners

• Matheon project B15: Large-scale integer linear programming problems.
• Matheon project C7: Application of the developed software for the optimization of electricty production in liberalized markets.


• Research Network NOPT: Exchange of models and software for the optimization of gas transport.
• TU Braunschweig, Marc Pfetsch: Second order cone constraints and infeasibility analysis.
• TU Darmstadt, Research Group Optimization: Development of an NLP infrastructure in SCIP and interface to the NLP solver DONLP.
• HU Berlin, Research Group A. Griewank: Expertise in NLP and AD.


• Siemens AG, Corporate Technology, Software & Engineering
  
• ILOG, an IBM company : Solution methods for generic mixed integer programming
• GAMS Development: Development of a GAMS interface to an extended SCIP version.