Collaborative Research: Advanced Techniques for Mixed-Integer Programming

这项研究将为0-1混合整数规划开发新的提升和投影方法。这些方法将包括两类技术。研究小组将考虑将n维点提升到n维超立方体的子集代数的Zeta向量，从而扩展了Lovasz-Schrijver，Sherali-Adams，Lasserre方法，以及Balas，Ceria和Cornuejols的析取编程(Lift And Project)方法。这样的提升看起来很有希望，因为它比前面提到的方法更快地产生更高维的对象。第二类技术将考虑连续细化析取以生成更深的切割平面。整数规划体现了在许多实际环境中出现的计划问题的系统解决方案，例如交通、物流、供应链、金融、发电等。这类问题本质上是非连续的：它们涉及资源的离散单位的分配。因此，它们是极其棘手的。同时，准确的解决方案转化为大量的节省，因此需要有效的解决方案方法。这项研究的影响将是扩大可以使用创新技术成功解决的问题的类别。

This research will develop new lift-and-project methods for 0-1 mixed-integer programming. These methods will encompass two classes of techniques. The research team will consider lifting an n-dimensional point to a zeta-vector of the subset algebra of the n-dimensional hypercube, thereby extending the Lovasz-Schrijver, Sherali-Adams, Lasserre methods, as well as the disjunctive programming ('lift and project') method of Balas, Ceria and Cornuejols. Such a lifting appears promising in that it produces higher-dimensional objects "faster" than the previously mentioned methods. The second class of techniques will consider successively refining a disjunction to generate deeper cutting planes.Integer programming embodies the systematic solution of planning problems arising in numerous practical settings, e.g. transportation, logistics, supply chain, finance, power generation and others. Such problems are inherently non-continuous: they involve the allocation of discrete units of resources. As such, they are extremely intractable. At the same time, accurate solutions translate into substantial savings, and thus there is a need for effective solution methodologies. The impact of this research will be to broaden the class of problems that can be successfully tackled, using innovative techniques.