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.

该奖项的研究目标是使用一种称为“复杂整数舍入”的新方法来创建和评估用于混合整数规划的新割平面方法。割平面是用于解决混合整数规划问题的算法的关键部分。混合整数规划是一种优化框架，在科学、工程和商业领域有着广泛的应用。所提出的方法包括推导三个主要元素的新颖形式并创新地使用它们：在应用于原始多面体的松弛/组合程序中使用基本多面体的一个或多个面和/或一个或多个子加法函数约束和一系列中间不等式，最终获得割生成函数。将考虑单约束和多约束切割，并将研究所开发切割的刻面定义属性。将研究对一系列重要的特殊结构问题进行定制化切割。为了评估所开发的切割的性能，将开发有效的分离方法并进行全面的计算实验。混合整数规划是一种强大而灵活的优化范例，在科学、工程和商业领域有着广泛的应用，从机组人员调度到分子生物学。然而，解决混合整数规划通常非常困难。通过引入新的强切割平面，这项研究如果成功，将带来更快的混合整数规划求解算法，并将增加我们能够解决的问题的规模。因此，它将对上述所有领域产生重大影响。此外，这项研究的方法论发展为有关切割平面方法的几种新研究途径打开了大门。