Investigations in Mixed Integer Programming

混合整数规划研究

• 批准号: 0800057
• 负责人: Eva Lee
• 金额: $ 39.08万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-01 至 2012-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0800057&HistoricalAwards=false
• 关键词: Investigations; Mixed; Integer; Programming

This grant provides funding for the investigation of theory and computational strategies for solving dense mixed integer programming (MIP) problems. Prior work has focused on sparse MIP problems, but in many applications of MIP technology, the MIP models are often dense. The research will investigate the facial structure of the independent set polytope via the construction of high-dimensional conflict hypergraphs. Specifically, various structures such as hyper-cliques, hyper-odd holes, hyper-odd antiholes, hyper-webs and hyper-antiwebs will be identified on the conflict hypergraph, and valid inequalities and facet-defining properties will be derived. To investigate the complexity, there will be an analysis on the ranks of the cutting planes associated with the hypergraphical structures. For computational strategies, the research will generalize a separation algorithm for identifying odd holes in hypergraphs, develop fast heuristics for generating the hyper-cliques, and implement the associated cutting planes within a parallel cutting plane and branch-and-cut environment to gauge their effectiveness and performance.If successful, the results of the research will advance the frontiers of knowledge in integer programming in several areas. First, it will lead to fundamental theoretical advances. Second, from a computational standpoint, it will offer new directions of research related to separation strategies for hypergraphic structures. The research will also have an impact in several application areas. Dense MIP problems arise naturally in many medical applications, including constrained discriminant analysis for medical diagnosis; brachytherapy cancer treatment; and medical imaging. The ability to solve the associated MIP problem instances will help to advance the medical frontiers. The research will also lead to advances in finance and business, including market-share problems, and the wide range of applications that involve classification (constrained discrimination), such as credit lending prediction, market trends, and consumer preference prediction.

该补助金为解决稠密混合整数规划（MIP）问题的理论和计算策略的研究提供资金。以前的工作集中在稀疏MIP问题，但在MIP技术的许多应用中，MIP模型往往是密集的。 该研究将通过构造高维冲突超图来研究独立集多面体的表面结构。具体地说，各种结构，如超团，超奇洞，超奇反洞，超网和超反网的冲突超图将被确定，有效的不等式和刻面定义的性质将被导出。为了研究复杂性，将对与超图结构相关联的切割平面的秩进行分析。在计算策略方面，本研究将归纳出一种识别超图中奇洞的分离算法，发展快速生成超团的算法，并在平行切割平面和分支切割环境中实现相关的切割平面，以衡量其有效性和性能，如果成功的话，本研究的结果将在多个领域推进整数规划的前沿知识。首先，它将导致基本的理论进步。其次，从计算的角度来看，它将提供新的研究方向与超图结构的分离策略。该研究还将在多个应用领域产生影响。 密集MIP问题在许多医学应用中自然出现，包括用于医学诊断的约束判别分析;近距离放射治疗癌症治疗;和医学成像。解决相关MIP问题实例的能力将有助于推进医学前沿。该研究还将导致金融和商业的进步，包括市场份额问题，以及涉及分类（约束歧视）的广泛应用，如信贷预测，市场趋势和消费者偏好预测。