Exact solutions to Linear and Integer Programming problems

Daniel Steffy
Assistant Professor

Date and Time: 

Wednesday, October 31, 2012 - 4:00pm

Event Location: 

Mohler Lab Room 451

The software systems commonly used to solve linear and integer programming problems today make use of oating-point computation and the inexactness of these computations can lead to errors in the returned results. Although such numerical errors are sometimes tolerable, there are situations when exact results are necessary. This talk will describe a variety of methods for computing exact solutions to LPs and MIPs over the rational numbers. A straightforward approach to obtain exact results could be to replace the oating-point operations in current software entirely by exact rational arithmetic; unfortunately, this approach can increase the running times dramatically, motivating the development of more sophisticated techniques. As an alternative, many recently developed methods use a hybrid approach, combining numeric and exact computation.

The key observation is that, although numerically obtained results are not necessarily correct, one can often extract useful information that can be used to reduce the number of exact computations necessary to arrive at an exact solution. We will start by describing an iterative renement procedure for computing extended precision and exact solutions to LPs. Arbitrarily precise solutions are computed by solving a sequence of closely related LPs with limited precision arithmetic. Exact arithmetic is used only for some inexpensive bookkeeping operations and to reconstruct the exact rational solution, either by rounding an approximate solution to a suitable rational representation or by recomputing the corresponding basic solution exactly. Next we discuss the use of hybrid methods for exact MIPs. In particular, within a branch-and-bound process, we compare dierent strategies for computing valid LP dual bounds. Extensive computational results will be presented showing that exact solutions can often be obtained without a large overhead, compared to inexact methods. (Includes joint work with Bill Cook, Ambros Gleixner, Thorsten Koch and Kati Wolter)

Bio Sketch: 

Dan Steffy is an Assistant Professor in the Department of Mathematics and Statistics at Oakland University in Rochester, MI. He received a Ph.D. in Algorithms, Combinatorics and Optimization from the Georgia Institute of Technology (2011), a M.A. (2005) and B.S. (2004) in Mathematics from Oakland University. Dr. Stey also spent one year as a post-doctoral researcher at the Zuse Institute Berlin. His research interests include Optimization, Operations Research and Computer Algebra.