Technical Note—A Class of Linear Programs Convertible to Network Problems

We consider a class of two-commodity network flow problems with additional, highly structured linear constraints in place of the usual capacity constraints. This class of linear programs arose as subproblems in a mixed integer programming formulation of a location model, and was solved by Ramakrishnan using a special purpose primal simplex algorithm. We show that, even though the constraint matrices of these problems are not transformable to constraint matrices of pure network problems, the problems themselves can be converted to pure network problems. The transformation depends on the existence of a set of variables whose non-negativity restrictions are redundant to the definition of the feasible region. We point out other situations in which such structure occurs.