bipolar orientations – Optimization Online

Improved optimization models for potential-driven network flow problems via ASTS orientations

Published: 2020/07/09

(Mixed) Integer Nonlinear Programming, Network Optimization asts orientations, bipolar orientations, combinatorial acyclicity models, mixed-integer nonlinear programming, potential-driven network flows

The class of potential-driven network flow problems provides important models for a range of infrastructure networks that lead to hard-to-solve MINLPs in real-world applications. On large-scale meshed networks the relaxations usually employed are rather weak due to cycles in the network. To address this situation, we introduce the concept of ASTS orientations, a generalization of … Read more

ASTS Orientations on Undirected Graphs: Structural analysis and enumeration

Published: 2020/06/20

Kai Helge Becker

Benjamin Hiller

Graphs and Matroids, Network Optimization acyclic orientations, bipolar orientations, combinatorial acyclicity models, enumeration algorithm, multiple sources and sinks

All feasible flows in potential-driven networks induce an orientation on the undirected graph underlying the network. Clearly, these orientations must satisfy two conditions: they are acyclic and there are no “dead ends” in the network, i.e. each source requires outgoing flows, each sink requires incoming flows, and each transhipment vertex requires both an incoming and … Read more