Solving singularly constrained generalized network problems

The singularly constrained generalized network problem represents a large class of capacitated linear programming (LP) problems. This class includes any LP problem whose coefficient matrix, ignoring single upper bound constraints, containsm + 1 rows which may be ordered such that each column has at most two non-zero entries in the firstm rows. The paper describes efficient procedures for solving such problems and presents computational results which indicate that, on large problems, these procedures are at least twenty-five times more efficient than the state of the art LP systemapex-iii.This research was partly supported by ONR Contract N00014-76-C-0383 with Decision Analysis and Research Institute and by Project NR047-021, ONR Contracts N00014-75-C-0616 and N00014-75-C-0569 with the Center for Cybernetic Studies, The University of Texas. Reproduction in whole or in part is permitted for any purpose of the United States Government.