Complex Integer Rounding Cuts for Mixed Integer Programming

混合整数规划的复杂整数舍入削减

• 批准号: 1100343
• 负责人: Kiavash Kianfar
• 金额: $ 20万
• 依托单位: Texas A&M Engineering Experiment Station
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-06-01 至 2014-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1100343&HistoricalAwards=false
• 关键词: Complex; Integer; Rounding; Cuts; Mixed

The research objective of this award is to create and evaluate new cutting plane methods for mixed integer programming using a new approach here called Complex Integer Rounding. Cutting planes are a crucial part of the algorithms used for solving mixed integer programming problems. Mixed integer programming is an optimization framework with numerous applications in science, engineering, and business. The proposed approach consists of deriving novel forms of three major elements and making innovative use of them: one or multiple facets of base polyhedra and/or one or multiple sub-additive functions are utilized within a relaxation/combination procedure which is applied on the original constraints and a series of intermediate inequalities to eventually obtain a cut generator function. Both single-constraint and multi-constraint cuts will be considered and facet-defining properties of the developed cuts will be investigated. The customization of the cuts to a collection of important special-structure problems will be studied. In order to evaluate performance of the developed cuts, efficient separation methods will be developed and comprehensive computational experiments will be performed.Mixed integer programming is a powerful and flexible optimization paradigm with ubiquitous applications in science, engineering, and business ranging from flight crew scheduling to molecular biology. Yet solving mixed integer programs is generally very difficult. Through introduction of new strong cutting planes, this research, if successful, will result in faster solution algorithms for mixed integer programming and will increase the size of the problems that we are able to solve. Consequently, it will have a significant impact on all aforementioned areas. Moreover, the methodological developments in this research open doors to several new research avenues regarding cutting plane methods.

该奖项的研究目标是使用称为复杂整数舍入的新方法创建和评估混合整数编程的新切割平面方法。切割平面是用于解决混合整数编程问题的算法的关键部分。混合整数编程是一个优化框架，具有科学，工程和业务中的许多应用程序。所提出的方法包括得出三个主要元素的新型形式，并对它们进行创新使用：基础Polyhedra的一个或多个方面和/或一个或多个亚添加功能在放松/组合过程中使用，该功能应用于原始约束和一系列中间体，以最终获得切割生成器功能。将考虑单构约束和多构造削减，并研究开发切割的方面定义特性。将研究将削减定制为重要的特殊结构问题集合。为了评估开发的切割的性能，将开发有效的分离方法，并将进行全面的计算实验。混合的整数编程是一种强大而灵活的优化范式，具有无处不在的科学，工程和业务，从飞行CREW计划到分子生物学。然而，解决混合整数程序通常非常困难。通过引入新的强切平面，这项研究（如果成功）将导致更快的解决方案算法用于混合整数编程，并将增加我们能够解决的问题的大小。因此，它将对上述所有区域产生重大影响。此外，这项研究中的方法论发展为有关切割平面方法的几种新研究途径打开了大门。