An Exact Rational Solver for Mixed Integer Programming

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