Theses and Dissertations from UMD

Permanent URI for this communityhttp://hdl.handle.net/1903/2

New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a give thesis/dissertation in DRUM

More information is available at Theses and Dissertations at University of Maryland Libraries.

Browse

Filters

20091

Settings

Author: search.filters.author.Nicholls, Stacey OneetaSubject: search.filters.subject.Linear Programming

Search Results

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Column Generation in Infeasible Predictor-Corrector Methods for Solving Linear Programs
    (2009) Nicholls, Stacey Oneeta; O'Leary, Dianne P.; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    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, AD2A T, where A \in \Re {m times n} and D2 = S{-1}X is a diagonal matrix. In cases when n >> m, 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 n constraints, we work with k = |Q| \in [m,n] constraints at each iteration, where Q is an index set consisting of the k most nearly active constraints at the current iterate. The cost of the formation of the matrix, AQ DQ2 AQT, reduces from &theta(m2 n) to &theta(m2 k) operations, where k is relatively small compared to n. 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.