LANCS Initiative Seminar Series - Exact Solutions in Linear and Integer Programming
Monday 17 May 2010, 11:00
LT6, Management School
Professor William J. Cook
Georgia Institute of Technology
Abstract: Numerous practical problems in operational research and other fields are formulated as linear or mixed-integer programming problems. 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 software is often satisfactory, accuracy can be important in many practical and theoretical settings. In this talk we treat the problem of finding exact rational solutions in this context. We describe computational results for benchmark LP instances, Kepler sphere-packing problems, coding-theory bounds, factoring integers, graph coloring, and the traveling salesman problem.
This talk is based on joint work with David Applegate, Sanjeeb Dash, Daniel Espinoza, Ricardo Fukasawa, Marcos Goycoolea, Stephan Held, and Dan Steffy.