  When the underlying physical network layer in optimal network flow problems
is a large graph, the associated optimization problem has a large set of
decision variables. In this paper, we discuss how the cycle basis from graph
theory can be used to reduce the size of this decision variable space. The idea
is to eliminate the aggregated flow conservation constraint of these problems
by explicitly characterizing its solutions in terms of the span of the columns
of the transpose of a fundamental cycle basis matrix of the network plus a
particular solution. We show that for any given input/output flow vector, a
particular solution can be efficiently constructed from tracing any path that
connects a source node to a sink node. We demonstrate our results over a
minimum cost flow problem as well as an optimal power flow problem with storage
and generation at the nodes. We also show that the new formulation of the
minimum cost flow problem based on the cycle basis variables is amenable to a
distributed solution. In this regard, we apply our method over a distributed
alternating direction method of multipliers (ADMM) solution and demonstrate it
over a numerical example.
