Polyhedral and Graph Theoretic Methods in Mixed Integer and Combinatorial Optimization

混合整数和组合优化中的多面体和图论方法

• 批准号: 0352885
• 负责人: Egon Balas
• 金额: $ 42万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-01 至 2007-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0352885&HistoricalAwards=false
• 关键词: Polyhedral; Graph; Theoretic; Methods; Mixed

This project addresses theoretical and computational aspects of integer programming and combinatorial optimization, using the tools of linear algebra and graph theory. It is focused on the approach called lift-and-project, developed in the nineties and recently incorporated into state-of-the-art software. Lift-and-project cuts are generated from a disjunction involving a combination of inequalities. One topic for investigation is how to simultaneously optimize the weighted combination of inequalities used in the disjunction underlying the cut, and the choice of multipliers in the monoidal strengthening of the resulting cut. Another topic in the same direction offers to improve the performance of Gomory cuts for mixed integer linear programs, by combining inequalities in well-defined ways. Other topics, aimed at understanding the structure of Lehman matrices and almost totally unimodular matrices, or an algorithm for finding an odd hole in a graph, are related to two important classes of problems: set packing and set covering. A better understanding of these classes of problems is a central aspect of the very active research currently occurring in the field of combinatorial optimization.To the extent that this project will be successful, it will advance the state of the art in mixed integer and combinatorial optimization, and thereby enhance our problem solving ability in a broad range of activities, from industrial production to logistics and telecommunications. The tools created here may be as useful in improving homeland security, as they may be instrumental in reinforcing our technological leadership. From the late fifties to the early nineties, integer programming was a way to formulate almost any optimization problem, yet the available computer codes could only handle toy problems of minuscule size. During the last decade the state of the art has radically changed, and today well over half of the integer programs formulated can also be solved. This project is expected to significantly accelerate this change.

本项目利用线性代数和图论的工具，研究整数规划和组合优化的理论和计算方面。它专注于一种名为Lift-and-Project的方法，该方法开发于90年代，最近被整合到最先进的软件中。提升和项目削减是从涉及不平等组合的析取中产生的。一个要研究的主题是如何同时优化在切割基础上的析取中使用的加权不等式组合，以及在所产生的切割的一元化强化中的乘子的选择。同一方向的另一个主题提出通过以明确定义的方式组合不等式来提高混合整数线性规划的Gomory割的性能。其他主题旨在理解Lehman矩阵和几乎完全么模矩阵的结构，或者寻找图中奇洞的算法，涉及两类重要的问题：集合填充和集合覆盖。更好地理解这类问题是目前在组合优化领域进行的非常活跃的研究的中心方面。该项目将在一定程度上成功地推进混合整数和组合优化的最新技术，从而提高我们在从工业生产到物流和电信等广泛活动中解决问题的能力。这里创造的工具在改善国土安全方面可能同样有用，因为它们可能有助于加强我们的技术领先地位。从五十年代末到九十年代初，整数规划是一种用来描述几乎任何优化问题的方法，但可用的计算机代码只能处理微小的玩具问题。在过去的十年里，技术水平发生了根本性的变化，今天，超过一半的整数规划也可以解决。该项目预计将大大加快这一变化。