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模型通常是密集的。 该研究将通过建造高维冲突超图研究独立集合的面部结构。具体而言，将在冲突超图上确定各种结构，例如超晶状体，超odd孔，超odd抗高位，超元素和超抗晶体，并得出有效的不平等和方面定义的特性。为了研究复杂性，将对与超图结构相关的切割平面的等级进行分析。对于计算策略，该研究将推广一种分离算法，以识别超图中的奇数，开发快速的启发式方法来产生超级液体，并在平行切割平面和分支和切割环境中实施相关的切割平面。首先，这将导致基本的理论进步。其次，从计算的角度来看，它将提供与超图结构的分离策略有关的研究方向。该研究还将在几个应用领域产生影响。 在许多医学应用中，自然出现了密集的MIP问题，包括用于医学诊断的判别分析；近距离放射治疗癌症治疗；和医学成像。解决相关MIP问题实例的能力将有助于进步医疗领域。这项研究还将导致金融和业务的进步，包括市场份额问题，以及涉及分类（受限制）的广泛应用，例如信用贷款预测，市场趋势和消费者偏好预测。