Mathematical Sciences: Investigations in Mixed Integer Programming

虽然近年来程序设计在理论和实践上都取得了显著的进步，但这些进步大多来自于纯0/1问题的解决。另一方面，混合问题，既有连续变量又有离散变量的问题--通常是0/1变量--在实践中占主导地位；此外，实践者经常制作这些模型的实例，而这些实例无法使用现有的代码来解决。这种在解决纯0/1问题方面的成功和对解决现实世界中困难混合问题的方法的现有需求的结合，在研究界得到了相当大的关注。然而，通用混合整数求解器仍然主要是求解器，虽然它们经常使用相当复杂的“启发式”装置，但它们仍然很少使用最近理论发展中隐含的算法思想。这项研究将试图通过制定一项研究规范来改变这种情况，该规范既包括在实践中取得成功的标准方法，也包括基于最近理论发展的想法。重点将放在实际解决作为一般混合整数程序出现但当前无法解决的真实世界实例上。

While recent years have seen remarkable progress in programming, both theoretically and practically, most of that progress has come in the solution of pure 0/1 problems. On the other hand, mixed problems, problems with both continuous and discrete variables-- usually 0/1 variables--dominate in practice; moreover, practitioners regularly produce instances of these models that cannot be solved using currently available codes. This combination of success in solving pure 0/1 problems and the existing demand for methods to solve difficult real-world mixed problems has received considerable attention in the research community. Nevertheless, general-purpose mixed-integer solvers remain primarily solvers, and while they often employ rather sophisticated ``heuristic'' devices, they still use few of the algorithmic ideas implicit in recent theoretical developments. This research will attempt to change that situation by developing a research code including both the standard methods that have been successful in practice, as well as incorporating ideas based upon recent theoretical developments. The focus will be on actually solving real-world instances that arise as general mixed integer programs but cannot currently be solved.