Collaborative Research: Web-Available Chvatal-Gomory Rank Determination and Optimization

合作研究：网络可用的 Chvatal-Gomory 排名确定和优化

• 批准号: 0457565
• 负责人: Craig Tovey
• 金额: --
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-06-01 至 2007-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0457565&HistoricalAwards=false
• 关键词: Collaborative; Research; Web; Available; Chvatal

This research project aims to develop algorithms and corresponding software tools to generate inequalities of low Chvatal-Gomory rank for integer programs. The algorithms will test inequalities to determine if they are of Chvatal-Gomory rank 0, 1, 2, or 3, and they will optimize over all rank 1 and 2 inequalities. Mixed integer optimization including polyhedral analysis and lattice-based approaches will be used as the central techniques to generate rank 1 inequalities and determine ranks 1 and 2. For rank 2 generation and rank 3 determination, a branch-and-price method will be explored with novel cut generation heuristics for warm starts. This work is part of a broader research program to understand and enhance the surprising effectiveness of small subsets of valid inequalities in integer programming. It will also advance understanding of Chvatal-Gomory rank and branch-and-price.The algorithms will be implemented using open-source computational optimization tools and will be made available for download under an open-source license. It is anticipated that they will provide a significant infrastructure component for integer programming theory and practice. They will help automate the generation of useful valid cuts, assess the potential of a formulation with rank 1 and rank 2 cuts, and help generalize specific cuts to classes of valid inequalities by providing their CG derivations. Making these general tools web-available will broaden the set of practitioners and researchers who can use sophisticated cutting plane methods effectively. This will contribute to more rapid solutions to integer programming problems in practice and may allow larger problems to be solved than is currently possible.

本研究计画的目的是发展产生整数规划低Chvatal-Gomory秩不等式的演算法与软体工具。 这些算法将测试不等式，以确定它们是Chvatal-Gomory秩为0、1、2还是3的不等式，并且它们将优化所有秩为1和2的不等式。混合整数优化，包括多面体分析和基于格的方法将被用作核心技术，以产生秩1不等式，并确定秩1和2。 对于秩2生成和秩3确定，将探索具有用于热启动的新颖切割生成算法的分支和价格方法。 这项工作是一个更广泛的研究计划的一部分，以了解和提高整数规划中有效不等式的小子集的惊人有效性。它还将促进对Chvatal-Gomory rank和branch-and-price的理解。这些算法将使用开源计算优化工具实现，并将在开源许可证下提供下载。 预计它们将为整数规划理论和实践提供重要的基础设施组件。 它们将有助于自动生成有用的有效切割，评估秩1和秩2切割的制定潜力，并通过提供CG推导来帮助将特定切割推广到有效不等式类。 使这些通用工具的网络将扩大从业人员和研究人员谁可以有效地使用复杂的切割平面方法。这将有助于更快地解决整数规划问题的实践中，并可能允许更大的问题，以解决比目前可能的。