Collaborative Research: Advanced Techniques for Mixed-Integer Programming

协作研究：混合整数规划的高级技术

• 批准号: 0200221
• 负责人: Daniel Bienstock
• 金额: $ 8.75万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-09-01 至 2004-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0200221&HistoricalAwards=false
• 关键词: Collaborative; Research; Advanced; Techniques; Mixed

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.

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