Dr. Benjamin Hiller

Projects as a project leader

• MI10

  Acyclic network flows

  Dr. Benjamin Hiller / Prof. Dr. Thorsten Koch / Prof. Dr. Martin Skutella

  Project heads: Dr. Benjamin Hiller / Prof. Dr. Thorsten Koch / Prof. Dr. Martin Skutella
  Project members: Dr. Kai-Helge Becker
  Duration: 01.06.2017 - 31.12.2019
  Status: running
  Located at: Konrad-Zuse-Zentrum für Informationstechnik Berlin
  

  Description

  Utility and infrastructure networks are at the heart of our daily life and we are taking their proper working for granted. To provide this service, network operators face difficult planning and operational problems. The complexity of the considered optimization problems increases for several reasons, for instance because geographically bigger networks are considered or the detail level is increased. For large networks, providing globally optimal solutions or at least good bounds for assessing solution quality is still a big challenge. This project addresses this challenge for so-called potential-driven nonlinear network flow problems that are a key model for infrastructure networks for fluids, e.g. water and gas. These problems feature a so-called potential for each node, and the flow on an arc is related to the difference of the potential of its end nodes. In particular, flow is always directed from higher to lower potential, i.e. the potentials induce an acylic orientation of the arcs. This observation is the motivation for this project: We study network flow problems with the additional requirement of acyclic flows: If each network arc is oriented in the direction of flow over this arc, then there is no directed cycle in the resulting network. This is an interesting combinatorial structure that arises from nonconvex nonlinear constraints and thus links combinatorial and continuous optimization. The aim of this project is to develop algorithmic techniques to exploit this structure to improve global optimization methods for large-scale nonlinear flow problems.
  
  http://www.zib.de/projects/acyclic-network-flows

• MI-AP5

  Combinatorial switching for routing gas flows

  Prof. Dr. Dr. h.c. mult. Martin Grötschel / Dr. Benjamin Hiller / Prof. Dr. Caren Tischendorf

  Project heads: Prof. Dr. Dr. h.c. mult. Martin Grötschel / Dr. Benjamin Hiller / Prof. Dr. Caren Tischendorf
  Project members: -
  Duration: 01.10.2014 - 30.06.2018
  Status: completed
  Located at: Humboldt Universität Berlin / Konrad-Zuse-Zentrum für Informationstechnik Berlin
  

  Description

  The goal of this subproject is to develop algorithmic fundamentals for the efficient treatment of switching decisions in gas networks. In particular, this involves the modelling and algorithmics of the switching operations in compressor stations, since these pose a significant source of modelling and runtime complexity. The set of feasible operating points of a compressor station is, in general, non-convex, in some circumstances even non-connected. However, it can be well approximated by the union of convex polyhedra. Hence, the treatment of such structures in MIPs and MINLPs will be the main focus of research in this subproject. While being motivated by the optimization of gas networks, the methods to be developed will be relevant for many applications of MIPs and MINLPs.
  Known techniques for modelling unions of polyhedra as the feasible set of a MIP rely on the inequality description of the underlying polyhedra. In contrast to this, another approach adapted to the geometric properties of the overall set can be considered. More precisely, the goal is to find and analyze a hierarchical description of a non-convex set that provides an as good as possible polyhedral relaxation on each level. This hierarchy can then be used by suitable branching strategies in the branch-and-bound procedure for solving MINLPs.
  In the long term, this subproject of SFB/TRR 154 is aiming at the development of real-time methods for obtaining combinatorial decisions. Furthermore, since the transient control of gas networks requires the successive solving of many similar MIPs/MINLPs, reoptimization techniques come into view that use known information from previous optimization problems in order to reduce running time. For these, a detailed analysis of the problem structure and a deeper understanding of the complex MIP/MINLP solving process will be an essential topic of research.
  
  http://trr154.fau.de/index.php/en/subprojects/a04e