Structure of Optimal Transport Networks Subject to a Global Constraint

The analysis and boundary optimal control of the nonlinear transport of gas on a network of pipelines is considered. The evolution of the gas distribution on a given pipe is modeled by an isothermal semilinear compressible Euler system in one space dimension. On the network, solutions satisfying (at nodes) the so called Kirchhoff flux continuity conditions are shown to exist in a neighborhood of an equilibrium state. The associated nonlinear optimization problem then aims at ...

We provide new results on the structure of optimal transportation networks obtained as minimizers of an energy cost functional consisting of a kinetic (pumping) and material (metabolic) cost terms, constrained by a local mass conservation law. In particular, we prove that every tree (i.e., graph without loops) represents a local minimizer of the energy with concave metabolic cost. For the linear metabolic cost, we prove that the set of minimizers contains a loop-free structur...

In many urban areas of the developing world, piped water is supplied only intermittently, as valves direct water to different parts of the water distribution system at different times. The flow is transient, and may transition between free-surface and pressurized, resulting in complex dynamical features with important consequences for water suppliers and users. Here, we develop a computational model of transition, transient pipe flow in a network, accounting for a wide variet...

Designing and optimizing different flows in networks is a relevant problem in many contexts. While a number of methods have been proposed in the physics and optimal transport literature for the one-commodity case, we lack similar results for the multi-commodity scenario. In this paper we present a model based on optimal transport theory for finding optimal multi-commodity flow configurations on networks. This model introduces a dynamics that regulates the edge conductivities ...

Branched Optimal Transport (BOT) is a generalization of optimal transport in which transportation costs along an edge are subadditive. This subadditivity models an increase in transport efficiency when shipping mass along the same route, favoring branched transportation networks. We here study the NP-hard optimization of BOT networks connecting a finite number of sources and sinks in $\mathbb{R}^2$. First, we show how to efficiently find the best geometry of a BOT network for...

We give a short overview of advantages and drawbacks of the classical formulation of minimum cost network flow problems and solution techniques, to motivate a reformulation of classical static minimum cost network flow problems as optimal control problems constrained by port-Hamiltonian systems (pHS). The first-order optimality system for the port-Hamiltonian system-constrained optimal control problem is formally derived. Then we propose a gradient-based algorithm to find opt...

In the presented study, a pipe penalization approach for the economic topology optimization of District Heating Networks is proposed, drawing inspiration from density-based topology optimization. For District Heating Networks, the upfront investment is a crucial factor for the rollout of this technology. Today, the pipe routing is usually designed relying on a linearization of the underlying heat transport problem. This study proposes to solve the optimal pipe routing problem...

We minimize the dissipation rate of an electrical network under a global constraint on the sum of powers of the conductances. We construct the explicit scaling relation between currents and conductances, and show equivalence to a a previous model [J. R. Banavar {\it et al} Phys. Rev. Lett. {\bf 84}, 004745 (2000)] optimizing a power-law cost function in an abstract network. We show the currents derive from a potential, and the scaling of the conductances depends only locally ...

In this manuscript we review new ideas and first results on application of the Graphical Models approach, originated from Statistical Physics, Information Theory, Computer Science and Machine Learning, to optimization problems of network flow type with additional constraints related to the physics of the flow. We illustrate the general concepts on a number of enabling examples from power system and natural gas transmission (continental scale) and distribution (district scale)...

Images of natural systems may represent patterns of network-like structure, which could reveal important information about the topological properties of the underlying subject. However, the image itself does not automatically provide a formal definition of a network in terms of sets of nodes and edges. Instead, this information should be suitably extracted from the raw image data. Motivated by this, we present a principled model to extract network topologies from images that ...