University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • View Item
    •   DRUM
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Column Generation in Infeasible Predictor-Corrector Methods for Solving Linear Programs

    Thumbnail
    View/Open
    Nicholls_umd_0117E_10121.pdf (792.1Kb)
    No. of downloads: 1155

    Date
    2009
    Author
    Nicholls, Stacey Oneeta
    Advisor
    O'Leary, Dianne P.
    Metadata
    Show full item record
    Abstract
    Primal &ndash dual interior &ndash point methods (IPMs) are distinguished for their exceptional theoretical properties and computational behavior in solving linear programming (LP) problems. Consider solving the primal &ndash dual LP pair using an IPM such as a primal &ndash dual Affine &ndash Scaling method, Mehrotra's Predictor &ndash Corrector method (the most commonly used IPM to date), or Potra's Predictor &ndash Corrector method. The bulk of the computation in the process stems from the formation of the normal equation matrix, <italic>AD<super>2</super>A <super>T</super></italic>, where <italic>A \in \Re <super>{m times n}</super></italic> and <italic>D<super>2</super> = S<super>{-1}</super>X</italic> is a diagonal matrix. In cases when <italic>n >> m</italic>, we propose to reduce this cost by incorporating a column generation scheme into existing infeasible IPMs for solving LPs. In particular, we solve an LP problem based on an iterative approach where we select a &ldquo small &rdquo subset of the constraints at each iteration with the aim of achieving both feasibility and optimality. Rather than <italic>n</italic> constraints, we work with <italic>k = |Q| \in [m,n]</italic> constraints at each iteration, where <italic>Q</italic> is an index set consisting of the <italic>k</italic> most nearly active constraints at the current iterate. The cost of the formation of the matrix, <italic>A<sub>Q</sub> D<sub>Q</sub><super>2</super> A<sub>Q</sub><super>T</super></italic>, reduces from <italic>&theta(m<super>2</super> n)</italic> to <italic>&theta(m<super>2</super> k)</italic> operations, where <italic>k</italic> is relatively small compared to <italic>n</italic>. Although numerical results show an occasional increase in the number of iterations, the total operation count and time to solve the LP using our algorithms is, in most cases, small compared to other &ldquo reduced &rdquo LP algorithms.
    URI
    http://hdl.handle.net/1903/9249
    Collections
    • Computer Science Theses and Dissertations
    • Mathematics Theses and Dissertations
    • UMD Theses and Dissertations

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility