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

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

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.