A New Class of Valid Inequalities for Nonlinear Network Design Problems

Please always quote using this URN: urn:nbn:de:0297-zib-17771
  • We consider a nonlinear nonconvex network design problem that arises in the extension of natural gas transmission networks. Given is such network with active and passive components, that is, valves, compressors, pressure regulators (active) and pipelines (passive), and a desired amount of flow at certain specified entry and exit nodes of the network. Besides flow conservation constraints in the nodes the flow must fulfill nonlinear nonconvex pressure loss constraints on the arcs subject to potential values (i.e., pressure levels) in both end nodes of each arc. Assume that there does not exist a feasible flow that fulfills all physical constraints and meets the desired entry and exit amounts. Then a natural question is where to extend the network by adding pipes in the most economic way such that this flow becomes feasible. Answering this question is computationally demanding because of the difficult problem structure. We use mixed-integer nonlinear programming techniques that rely on an outer approximation of the overall problem, and a branching on decision variables. We formulate a new class of valid inequalities (or cutting planes) which reduce the overall solution time when added to the formulation. We demonstrate the computational merits of our approach on test instances.

Download full text files

Export metadata

  • Export Bibtex
Author:Jesco Humpola, Armin Fügenschuh
Document Type:ZIB-Report
Tag:Cutting Planes; Mixed-Integer Nonlinear Programming; Network Design
Date of first Publication:2013/02/16
Series (Serial Number):ZIB-Report (13-06)
Published in:Appeared in: OR Spectrum 2015
Licence (German):License LogoCreative Commons - Namensnennung-Nicht kommerziell-Keine Bearbeitung

$Rev: 13581 $