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问题实例的能力将有助于推进医学前沿。该研究还将导致金融和商业领域的进步，包括市场份额问题，以及涉及分类（约束歧视）的广泛应用，如信贷预测、市场趋势和消费者偏好预测。