An efficient simplex-based method for solving large linear programs

Abstract

A simplex-based method of solving specific classes of large-scale linear programs is presented. The structure of both staircase and block-angular linear programs is exploited to construct an advanced or "crash" basis to be used with a simplex-based linear program solver. First, the constraint matrix is decomposed into blocks. In contrast to many other systems that require additional information about the form of the linear program, the method described here determines this decomposition without prior knowledge of the matrix structure. As the problem of automatically finding such a decomposition is NP-complete, a heuristic is used to discover blocks within the constraint matrix. After a decomposition of the constraint matrix is determined, smaller linear programs called subproblems are formed. These subproblems are solved using a simplex-based solver, and the solution information is used to construct an advanced or "crash" basis for the original linear program. In contrast to decomposition methods that iteratively solve subproblems to obtain a solution to the original problem, this approach requires solving each subproblem at most twice. Finally, the original linear program is solved by providing the advanced basis to a simplex-based solver. Results indicate that this method solves some large linear programs much faster than state-of-the-art simplex-based solvers do. For example, for a set of linear programs that range in size from 5,000 x 9,000 to 30,000 x 50,000 constraints and variables, the presented method solves each linear program in about a tenth the number of simplex iterations. This reduces the total time required to solve each linear program by a factor of from two to five.