Collaborative Research: Advanced Techniques for Mixed-Integer Programming

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

• 批准号: 0200308
• 负责人: Gabor Pataki
• 金额: $ 8.74万
• 依托单位: University of North Carolina at Chapel Hill
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-09-01 至 2005-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0200308&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，拉瑟尔方法，以及Balas，Ceria和Cornuejols的析取编程（'提升和投影'）方法。 这种提升看起来很有希望，因为它比前面提到的方法“更快”地产生高维对象。 第二类技术将考虑连续地改进一个析取以产生更深的切割平面。可编程规划体现了在许多实际环境中出现的规划问题的系统解决方案，例如运输，物流，供应链，金融，发电等。 这类问题本质上是不连续的：它们涉及分散的资源单位的分配。 因此，它们极其棘手。 与此同时，准确的解决方案转化为大量的节省，因此需要有效的解决方法。 这项研究的影响将是扩大可以成功解决的问题，使用创新技术的类。