Back to search

Georgia Institute of Technology

Topics in exact precision mathematical programming

Abstract

dc:description.abstract

The focus of this dissertation is the advancement of theory and computation related to exact precision mathematical programming. Optimization software based on floating-point arithmetic can return suboptimal or incorrect resulting because of round-off errors or the use of numerical tolerances. Exact or correct results are necessary for some applications. Implementing software entirely in rational arithmetic can be prohibitively slow. A viable alternative is the use of hybrid methods that use fast numerical computation to obtain approximate results that are then verified or corrected with safe or exact computation. We study fast methods for sparse exact rational linear algebra, which arises as a bottleneck when solving linear programming problems exactly. Output sensitive methods for exact linear algebra are studied. Finally, a new method for computing valid linear programming bounds is introduced and proven effective as a subroutine for solving mixed-integer linear programming problems exactly. Extensive computational results are presented for each topic.

Degree

thesis:*
Department dc:contributor.department
Algorithms, Combinatorics, and Optimization
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2011

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Steffy, Daniel E.
Advisor dc:contributor.advisor
  • Cook, William J.
Committee members dc:contributor.committeemember
  • Nemhauser, George L.
  • Robin Thomas
  • Dey, Santanu
  • Ahmed, Shabbir
  • Gu, Zonghao

Subjects

dc:subject × 7

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/39639

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Steffy, Daniel E.. Topics in exact precision mathematical programming. Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/39639