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.
