Topics in exact precision mathematical programming

The field of Mathematical Programming offers a range of tools and algorithms to solve optimization problems. Software based on these ideas is used in many application areas to solve real world decision problems. However, few available software packages provide any guarantee of correct answers or certification of results, despite their widespread use. Computations are typically performed entirely in floating-point arithmetic where attempts are made to satisfy feasibility and optimality conditions approximately instead of exactly.;The focus of this dissertation is the advancement of theory and computation related to exact precision mathematical programming. We will specifically consider linear programming (LP) and mixed-integer programming (MIP) problems. Implementing software which relies entirely on exact arithmetic could give prohibitive slowdown compared to inexact methods so we make use of hybrid symbolic-numeric computation. In this paradigm algorithms are designed to use fast inexact arithmetic for many operations and then correct or verify the results using safe or exact computation.;In Chapter 1 we will further motivate the topic of this dissertation by describing different types of errors that can result from the use of floating-point arithmetic. We will also describe a range of applications where numerical errors are unacceptable.;In Chapter 2 we present new results in symbolic linear algebra. We study output-sensitive algorithms to solve rational linear systems of equations. These algorithms have the same worst case performance as conventional methods but are guaranteed to terminate early when the exact rational solution has a small representation. These techniques were motivated by experiments performed on linear systems arising when solving exact LPs.;In Chapter 3 we investigate solving very sparse rational linear systems of equations which arise as a bottleneck in solving exact LPs. A computational study is performed comparing four different techniques for exact rational system solving on a wide range of instances arising from applied problems.;Chapter 4 describes a new algorithm to compute valid LP bounds by correcting approximate solutions. This algorithm is designed to be used in the MIP setting and accelerates bound computations by reusing structural information throughout a branch-and-bound tree. We show this method to be more general than some algorithms previously described for this purpose. Computational experiments are performed to demonstrate its effectiveness.;In Chapter 5 we discuss future directions for research in exact mathematical programming including challenges, opportunities and new application areas.