Rice Univesrity Logo
    • FAQ
    • Deposit your work
    • Login
    View Item 
    •   Rice Scholarship Home
    • Rice University Graduate Electronic Theses and Dissertations
    • Rice University Electronic Theses and Dissertations
    • View Item
    •   Rice Scholarship Home
    • Rice University Graduate Electronic Theses and Dissertations
    • Rice University Electronic Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    An efficient simplex-based method for solving large linear programs

    Thumbnail
    Name:
    9610632.PDF
    Size:
    3.554Mb
    Format:
    PDF
    View/Open
    Author
    Dadmehr, Shireen Sara
    Date
    1995
    Advisor
    Bixby, Robert E.
    Degree
    Doctor of Philosophy
    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.
    Keyword
    Mathematics
    Citation
    Dadmehr, Shireen Sara. "An efficient simplex-based method for solving large linear programs." (1995) Diss., Rice University. https://hdl.handle.net/1911/16813.
    Metadata
    Show full item record
    Collections
    • Rice University Electronic Theses and Dissertations [13409]

    Home | FAQ | Contact Us | Privacy Notice | Accessibility Statement
    Managed by the Digital Scholarship Services at Fondren Library, Rice University
    Physical Address: 6100 Main Street, Houston, Texas 77005
    Mailing Address: MS-44, P.O.BOX 1892, Houston, Texas 77251-1892
    Site Map

     

    Searching scope

    Browse

    Entire ArchiveCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsTypeThis CollectionBy Issue DateAuthorsTitlesSubjectsType

    My Account

    Login

    Statistics

    View Usage Statistics

    Home | FAQ | Contact Us | Privacy Notice | Accessibility Statement
    Managed by the Digital Scholarship Services at Fondren Library, Rice University
    Physical Address: 6100 Main Street, Houston, Texas 77005
    Mailing Address: MS-44, P.O.BOX 1892, Houston, Texas 77251-1892
    Site Map