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.

This is a joint project with:

• Humboldt-Universität zu Berlin
• Weierstrass Institute for Applied Analysis and Stochastics

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.

The vision of this project is to advance the rapid specification and efficient solution of mixed-integer nonlinear programs with chance constraints which will have a broad impact on industrial and academic projects inside and outside of Matheon.

• Martin Grötschel
• René Henrion, WIAS
• Thorsten Koch (Contact)
• Werner Römisch, HU Berlin

• Thomas Arnold, WIAS
• Timo Berthold
• Stefan Heinz
• Stefan Vigerske, HU Berlin

• Tobias Achterberg
• Armin Fügenschuh
• Ambros M. Gleixner
• Kati Wolter

• CPAIOR 2011 (May 23 - 27)
  8th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems

2012

• Comparing MIQCP solvers to a specialised algorithm for mine production scheduling
  Andreas Bley, Ambros M. Gleixner, Thorsten Koch, and Stefan Vigerske
  In: H.G. Bock and X.P. Hoang and R. Rannacher and J. Schlöder (Eds.), Modeling, Simulation and Optimization of Complex Processes - Proc. of 4th Int. Conf. on High Performance Scientific Computing, pages 25-39, 2012.
• Extending a CIP framework to solve MIQCPs
  Timo Berthold, Stefan Heinz, and Stefan Vigerske
  In: J. Lee and S. Leyffer (Eds.), Mixed Integer Nonlinear Programming, The IMA Volumes in Mathematics and its Applications, Volume 154, pages 427–444, 2012.

2011

• Rounding and propagation heuristics for mixed integer programming
  Tobias Achterberg, Timo Berthold, and Gregor Hendel
  In Proc. of OR2011, to appear. Matheon Preprint #858.
• Large neighborhood search beyond MIP
  Timo Berthold, Stefan Heinz, Marc E. Pfetsch, and Stefan Vigerske
  In L. Di Gaspero, Andrea S., and T. Stützle (Eds.), Proc. of MIC 2011, pages 51–60, 2011.
• An exact rational mixed-integer programming solver
  William Cook, Thorsten Koch, Daniel E. Steffy, and Kati Wolter 
  IPCO 2011: The 15th Conference on Integer Programming and Combinatorial Optimization, LNCS 6655, 104–116, 2011. 
• MIPLIB 2010
  Thorsten Koch, Tobias Achterberg, Erling Andersen, Oliver Bastert, Timo Berthold, Robert E. Bixby, Emilie Danna, Gerald Gamrath, Ambros M. Gleixner, Stefan Heinz, Andrea Lodi, Hans Mittelmann, Ted Ralphs, Domenico Salvagnin, Daniel E. Steffy, and Kati Wolter  
  In: Mathematical Programming Computation, Volume 3, Number 2, pages 103–163, 2011.  
• Explanations for the cumulative constraint: an experimental study
  Stefan Heinz and Jens Schulz
  In: P.M. Pardalos and S. Rebennack (Eds.), Experimental Algorithms –  SEA 2011, LNCS 6630, pages 400–409.
  
• An approximative criterion for the potential of energetic reasoning
  Timo Berthold, Stefan Heinz, and Jens Schulz
  In: A. Marchetti-Spaccamela and M. Segal (Eds.), Theory and Practice of Algorithms in (Computer) Systems (TAPAS 2011), LNCS 6595, pages 229–239.
  

2010

• Optimizing the design of complex energy conversion systems by branch and cut
  Turang Ahadi-Oskui, Stefan Vigerske, Iwo Nowak, and George Tsatsaronis
  Computers & Chemical Engineering 34(8):1226–1236.
• MINLP solver software
  Michael R. Bussieck and Stefan Vigerske
  In: J. J. Cochran et.al., editor, Wiley Encyclopedia of Operations Research and Management Science. Wiley & Sons, Inc.
• Rapid learning for binary programs
  Timo Berthold, Thibaut Feydy, and Peter J. Stuckey
  In: A. Lodi, M. Milano, and P. Toth (Eds.), Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems – CPAIOR 2010; LNCS 6140, pages 51–55.
  
• A Constraint Integer Programming Approach for Resource-Constrained Project Scheduling 
  Timo Berthold, Stefan Heinz, and , Marco E. Lübbecke, Rolf H. Möhring, and Jens Schulz 
  In: A. Lodi, M. Milano, and P. Toth (Eds.), Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems – CPAIOR 2010; LNCS 6140, pages 313–317.
  
• Undercover – a primal heuristic for MINLP based on sub-MIPs generated by set covering
  Timo Berthold and Ambros M. Gleixner
  In: P. Bonami, L. Liberti, A. J. Miller, and A. Sartenaer (Eds.), Proceedings of the EWMINLP, pages 103–112.
  
• Supporting global numerical optimization of rational functions by generic symbolic convexity tests 
  Winfried Neun, Thomas Sturm, and Stefan Vigerske 
  In: Proceedings of the 12th international conference on Computer algebra in scientific computing – CASC'10; pages 205–219.
  

2009

• Hybrid Branching
  Tobias Achterberg and Timo Berthold 
  In: W. van Hoeve and J. N. Hooker, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems – CPAIOR 2009; LNCS 5547, pages 309–311.
• SCIP: Solving Constraint Integer Programs
  Tobias Achterberg
  Mathematical Programming Computation Nr. 1(1), pages 1–41.
• Nonlinear pseudo-Boolean optimization: relaxation or propagation?
  Timo Berthold, Stefan Heinz, and Marc E. Pfetsch
  In: O. Kullmann (Eds.), Theory and Applications of Satisfiability Testing –  SAT 2009; LNCS 5584, pages 441–446.
  

• Undercover – a primal MINLP heuristic exploring a largest sub-MIP 
  Timo Berthold and Ambros M. Gleixner
  ZIB Report 12-07.
• On the computational impact of MIQCP solver components
  Timo Berthold, Ambros M. Gleixner, Stefan Heinz, and Stefan Vigerske
  ZIB Report 11-01.
• ParaSCIP – a parallel extension of SCIP
  Yuji Shinano, Tobias Achterberg, Timo Berthold, Stefan Heinz, and Thorsten Koch
  ZIB Report 10-27.

• DFG Research Center Matheon "Mathematics for key technologies", Projekt B15: Large-scale integer linear programming problems.
• DFG Research Center Matheon "Mathematics for key technologies", Projekt B25: Scheduling Techniques in Constraint Integer Programming.
• DFG Research Center Matheon "Mathematics for key technologies", Projekt C7: Evaluationalgorithms and Error Estimates for Gradients of Distribution Functions in Chance Constraints
  
  
• Research Cooperation Network Optimization ForNe: Exchange of models and software for the optimization of gas transport.
• TU Braunschweig, Marc Pfetsch: Second order cone constraints and infeasibility analysis.
• Friedrich-Alexander-Universität Erlangen-Nürnberg, Chair of EDOM: Decomposition of Constraint Integer Programs
  
  
• Siemens AG, Corporate Technology: Development of SCIP and SoPlex
  
• IBM ILOG Optimization: Solution methods for generic mixed integer programming
• GAMS Development: Development of a GAMS interface to an extended SCIP version.

DFG Research Center Matheon "Mathematics for key technologies: Modelling, simulation, and optimization of real-word processes."

05/2009 - 05/2014