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问题实例的能力将有助于推进医学前沿。这项研究还将促进金融和商业的进步，包括市场份额问题，以及涉及分类(约束判别)的广泛应用，如信贷贷款预测、市场趋势和消费者偏好预测。