Optimization Online


A New Class of Valid Inequalities for Nonlinear Network Design Problems

Armin F├╝genschuh(fuegenschuh***at***zib.de)
Jesco Humpola(humpola***at***zib.de)

Abstract: 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.

Keywords: Cutting Planes; Mixed-Integer Nonlinear Programming; Network Design

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation: Zuse Institute Technical Report ZR-13-06 urn:nbn:de:0297-zib-17771

Download: [PDF]

Entry Submitted: 02/19/2013
Entry Accepted: 02/19/2013
Entry Last Modified: 02/19/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society