Show simple item record

dc.contributor.advisor Bixby, Robert E.
dc.creatorDadmehr, Shireen Sara
dc.date.accessioned 2009-06-04T00:05:18Z
dc.date.available 2009-06-04T00:05:18Z
dc.date.issued 1995
dc.identifier.urihttp://hdl.handle.net/1911/16813
dc.description.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.
dc.format.extent 110 p.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectMathematics
dc.title An efficient simplex-based method for solving large linear programs
dc.type.genre Thesis
dc.type.material Text
thesis.degree.department Mathematics
thesis.degree.discipline Natural Sciences
thesis.degree.grantor Rice University
thesis.degree.level Doctoral
thesis.degree.name Doctor of Philosophy
dc.identifier.citation Dadmehr, Shireen Sara. "An efficient simplex-based method for solving large linear programs." (1995) Diss., Rice University. http://hdl.handle.net/1911/16813.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record