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.