An Exact Rational Solver for Mixed Integer Programming

该项目的中心是创建方法和计算机代码，用于在有理数运算中精确解决混合整数规划问题。 混合整数规划是应用运筹学中广泛使用的工具，它提供了捕捉本质上离散的决策的模型。 一个精确的理性求解器可以为这些模型提供可证明的最优解，避免现有软件中使用的浮点计算中固有的不准确性。 该研究计划考虑有效混合整数舍入不等式的生成以改进公式、混合背包多面体的精确分离、使用收紧方法来改进群松弛的不等式、旅行工作中采用的试探性分支-推销员问题、可行性问题的分支方法、分支定界树的支配技术、无理目标函数的扩展、以及对有理线性规划的现有求解技术的改进。 作为具体的测试床的工作，标准库的实例收集从工业和学术来源，以及模型的整数因子分解和模型中产生的松弛的旅行推销员problem.The有效的不等式和分支技术的一般性研究将推进当前一代的混合整数规划求解器的解决方案的能力。 特别是，在这项工作中开发的精确的理性求解器将扩展混合整数规划的应用程序，需要准确的解决方案。 该项目产生的计算机实现将提供给研究界，为运筹学和其他领域的应用和理论工作提供资源。 参与这项工作的研究生将接受大型模型实际解决方案的先进技术培训。 一个Windows图形用户界面的精确求解器将被开发用于本科和高中教育。

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.