Solving Singly Constrained Transshipment Problems

This paper develops a primal simplex procedure to solve transshipment problems with an arbitrary additional constraint. The procedure incorporates efficient methods for pricing-out the basis, determining certain key vector representations, and implementing the change of basis. These methods exploit the near triangularity of the basis in a manner that takes advantage of computational schemes and list structures used to solve the pure transshipment problem. We have implemented these results in a computer code, I/OPNETS-I. Computational results (necessarily limited) confirm that this code is significantly faster than APEX-III on some large problems. We have also developed a fast method for determining near optimal integer solutions. Computational results show that the near optimum integer solution value is usually within 0.5% of the value of the optimum continuous solution value.