Many problems in discrete optimization 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. The use of such software makes it difficult to interpret computational work on the exact solution of model instances. In this talk we treat the problem of finding exact rational solutions in this context. We describe computational results for benchmark LP instances, mixed-integer-programming models, Kepler sphere-packing problems, graph coloring, and the traveling salesman problem. This talk is based on joint work with Stephan Held, Thorsten Koch, Dan Steffy, and Kati Wolter.
Copyright. All Rights Reserved.