Linear and mixed-integer programming are powerful tools for modeling and solving a wide range of decision problems. Despite their widespread use, few available software packages provide any guarantee of correct answers. Possible inaccuracy is caused by the use of floating-point numbers. This talk will present new results related to efficiently solving linear and mixed-integer programming problems exactly over the rational numbers. Relying entirely on exact arithmetic can cause a prohibitive slowdown, 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. We study fast methods for sparse exact linear algebra, which arises as a bottleneck when solving linear programming problems exactly. Additionally, a new method for computing valid linear programming bounds is introduced and proven effective as a subroutine for solving mixed-integer programming problems exactly. Extensive computational results are presented for each topic.  (Includes joint work with W. Cook, T. Koch and K. Wolter)

Friday, February 11, 2011

3:30 – 4:30 P.M.

372 Science and Engineering Building

(Refreshments at 3:00-3:30 PM in the kitchen area adjacent to 368 SEB)