Numerically Accurate Solutions in Linear and Integer Programming
<-- Return to the list
Date: 04-29-2008
Start Time:
1:00pm
End Time: 2:00pm
Speaker: William Cook, Georgia Institute of Technology
Location: Mudd 303
ABSTRACT
Numerous practical computational problems are formulated as instances of linear or mixed-integer programming. These models are typically described with rational data, while solution software uses floating-point arithmetic and inexact linear algebra to obtain approximate results. Although such solutions are satisfactory in applications, accuracy can be important in many practical and theoretical settings. An important example is the heavy use of linear programming in Hales' proof of the Kepler Conjecture concerning the packing of spheres in three dimensions.
In this talk we treat the problem of finding exact rational solutions to linear and mixed-integer programming models. We describe computational results for benchmark instances, Kepler models, coding-theory bounds, factoring integers, and the traveling salesman problem.
This talk is based on joint work with David Applegate, Sanjeeb Dash, Daniel Espinoza, Ricardo Fukasawa, Marcos Goycoolea, and Dan Steffy.
BIO
TBA