In this paper, we use the cycle basis from graph theory to reduce the size of the decision variable space of optimal network flow problems by eliminating the aggregated flow conservation constraint. We use a minimum c...In this paper, we use the cycle basis from graph theory to reduce the size of the decision variable space of optimal network flow problems by eliminating the aggregated flow conservation constraint. We use a minimum cost flow problem and an optimal power flow problem with generation and storage at the nodes to demonstrate our decision variable reduction method.The main advantage of the proposed technique is that it retains the natural sparse/decomposable structure of network flow problems. As such, the reformulated problems are still amenable to distributed solutions. We demonstrate this by proposing a distributed alternating direction method of multipliers(ADMM)solution for a minimum cost flow problem. We also show that the communication cost of the distributed ADMM algorithm for our proposed cycle-based formulation of the minimum cost flow problem is lower than that of a distributed ADMM algorithm for the original arc-based formulation.展开更多
基金supported by National Science Foundation award ECCS-1653838
文摘In this paper, we use the cycle basis from graph theory to reduce the size of the decision variable space of optimal network flow problems by eliminating the aggregated flow conservation constraint. We use a minimum cost flow problem and an optimal power flow problem with generation and storage at the nodes to demonstrate our decision variable reduction method.The main advantage of the proposed technique is that it retains the natural sparse/decomposable structure of network flow problems. As such, the reformulated problems are still amenable to distributed solutions. We demonstrate this by proposing a distributed alternating direction method of multipliers(ADMM)solution for a minimum cost flow problem. We also show that the communication cost of the distributed ADMM algorithm for our proposed cycle-based formulation of the minimum cost flow problem is lower than that of a distributed ADMM algorithm for the original arc-based formulation.
