IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

Computational Experience with Linear Optimization and Related Problems

Show full item record

Bookmark or cite this item:

Files in this item

File Description Format
PDF 1_Elble_Joseph.pdf (5MB) (no description provided) PDF
Title: Computational Experience with Linear Optimization and Related Problems
Author(s): Elble, Joseph M.
Director of Research: Sahinidis, Nikolaos V.
Doctoral Committee Chair(s): Sahinidis, Nikolaos V.
Doctoral Committee Member(s): Palekar, Udatta S.; Peng, Jiming; Shanbhag, Uday V.
Department / Program: Industrial&Enterprise Sys Eng
Discipline: Industrial Engineering
Degree Granting Institution: University of Illinois at Urbana-Champaign
Degree: Ph.D.
Genre: Dissertation
Subject(s): linear optimization linear systems high performance computing
Abstract: The computational aspects of the simplex algorithm are investigated, and high performance computing is used to enhance the computational performance of analogous algorithms for linear systems. It is wellknown that the efficiency of mathematical optimization software is integrally linked to the preprocessing techniques employed by software. Existing preprocessing techniques are reviewed, and the relative cost and effectiveness of these techniques are explored. Scaling is the most common preconditioning technique utilized in linear optimization solvers. Existing techniques for obtaining scaling factors for linear systems are investigated, and it is discovered that, on average, no scaling technique outperforms the simplest technique, i.e., equilibration, despite the added complexity and computational cost. Furthermore, simply applying techniques that work well in practice for linear systems (i.e., solving Ax = b, where A is an n x n matrix with full-rank and b is an n-vector) is not a solution to the underlying problem of scaling a linear program. A small computational study depicts the effectiveness of the Orchard-Hays triangularization technique in preordering a simplex basis for factorization. Pricing and pivoting in the simplex algorithm involve selecting an entering and exiting variable at each iteration. Several existing pricing procedures are reviewed, and new procedures are proposed. These procedures are capable of reducing the number of simplex iterations. By prohibiting specific variables from repeatedly re-entering the basis, degenerate cycles can be avoided. This phenomenon is computationally analyzed using several modern test problems. High performance computing is investigated for several related linear problems. A composite-Jacobi binormalization algorithm is developed for the graphics processing unit. It is shown that this algorithm achieves a six-fold improvement in performance relative to the corresponding CPU implementation. The graphics processing unit is used to solve large linear systems derived from partial differential equations. Well-known indirect methods are studied, and the results demonstrate that a graphics processing unit implementation of CGNR (conjugate gradient normal residual) is capable of out-performing a state-of-the-art parallel implementation of a specialized algorithm designed for a 16-node Linux cluster. The computational results demonstrate that the graphics processing unit offers a low-cost and high-performance computing solution for solving large-scale partial differential equations.
Issue Date: 2010-08-20
Rights Information: Copyright 2010 Joseph Elble
Date Available in IDEALS: 2010-08-20
Date Deposited: 2010-08

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 482
  • Downloads this Month: 3
  • Downloads Today: 1


My Account


Access Key