Improved optimization models for potential-driven network flow problems via ASTS orientations
Please always quote using this URN:urn:nbn:de:0296-matheon-14324
- The class of potential-driven network flow problems provides important models for a range of infrastructure networks. For real-world applications, they need to be combined with integer models for switching certain network elements, giving rise to hard-to-solve MINLPs. We observe that on large-scale real-world meshed networks the relaxations usu- ally employed are rather weak due to cycles in the network. To address this situation, we introduce the concept of ASTS orientations, a generalization of bipolar orientations, as a combinatorial relaxation of feasible solutions of potential-driven flow problems, study their structure, and show how they can be used to strengthen existing relaxations and thus provide improved optimization models. Our computational results indicate that ASTS orientations can be used to derive much stronger bounds on the flow variables than existing bound tightening methods. We also show that our proposed model extensions yield significant performance improvements for an existing state-of-the-art MILP model for large-scale gas networks.
Author: | Kai Helge Becker, Benjamin Hiller |
---|---|
URN: | urn:nbn:de:0296-matheon-14324 |
Referee: | Ralf Borndörfer |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2019/12/11 |
Release Date: | 2019/12/11 |
Tag: | ASTS orientations; bipolar orientations; mixed-integer nonlinear programming; potential-driven network flows |
Institute: | Zuse Institute Berlin (ZIB) |
Project: | B Networks / B-MI10 Acyclic network flows |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C30 Nonlinear programming |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C35 Programming involving graphs or networks [See also 90C27] | |
Preprint Number: | 1128 |