The linear balancing flow problem

The original motivation for investigating the Linear Balancing Flow Problem (LBFP) came from the optimization of a real-life production plan. Each instance of LBFP is a linear programming problem and can be interpreted as a flow problem on a bipartite network with gains. In the literature the typical flow probelm on networks with gains is either a max flow or a min cost flow problem. Here the authors consider a different kind of objective, namely, how to optimally balance the flow out of a given set of nodes. An original algorithm is suggested which takes advantage of the particular problem structure. Theoretically it may be viewed as a specialized version of the Simplex. However it is more efficient than the latter: in fact, it requires much less memory and computing time. The key feature consists in associating a tree to the set of variables of the dual problem that are out of the current basis. The justification of the proposed algorithm does not immediately follow from that of the Simplex. A direct proof of its validity is provided and simple numerical examples are reported.