An Exact Rational Solver for Mixed Integer Programming

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

The project centers on the creation of methodology and computer codes for the exact solution of mixed-integer programming problems in rational arithmetic. Mixed-integer programming is a widely used tool in applied operations research, providing models that capture decisions that are discrete in nature. An exact rational solver can deliver provably optimal solutions to these models, avoiding the inaccuracies inherent in the floating-point computations used in existing software. The research program considers the generation of valid mixed-integer rounding inequalities to improve formulations, the exact separation of mixed-knapsack polyhedra, the use of tightening methods to improve inequalities from group relaxations, tentative branching adopted from work on the traveling salesman problem, branching methods for feasibility problems, domination techniques for branch-and-bound trees, extensions for irrational objective functions, and improvements in existing solution techniques for rational linear programming. As specific test beds for the work, standard libraries of instances gathered from industrial and academic sources will be considered, as well as models for factoring integers and models arising in relaxations of the traveling salesman problem. The general study of valid inequalities and branching techniques will advance the solution capabilities of the current generation of mixed-integer programming solvers. In particular, the exact rational solver developed in this work will extend the reach of mixed-integer programming in applications that demand accurate solutions. Computer implementations resulting from the project will be made available to the research community, providing a resource for applied and theoretical work in operations research and other fields. Graduate students involved in this work will receive training in advanced techniques in the practical solution of large-scale models. A Windows graphical-user-interface for the exact solver will be developed for adoption in undergraduate and high-school education.