CG-rank

CG-rank is an open-source program that tests inequalities to determine whether their Chvatal-Gomory rank is 0, 1, 2, or greater. It is based on research by Brady Hunsaker, Craig Tovey, and Ellis Johnson. The coding was done by Brady Hunsaker.

The research underlying the software has been supported by NSF grant DMI-0500045.

Description

CG-rank takes as input an integer program and a set of constraints. For each constraint, it determines whether it has Chvatal-Gomory rank 0, 1, 2, or greater than 2 for the given integer program.

In the cases of ranks 0, 1, and 2, a set of certificates is output that can be used to verify the result.

CG-rank requires two other open-source packages: COIN-OR (OSI and CLP) and GLPK.

I did a presentation on CG-rank at the INFORMS Computing Society 2005 conference in Annapolis. It provides an introduction: CG-rank presentation (770K). Note that only the rank determination part of the code is in this release. I am planning to release the separation/optimization version of the code once I have improved and polished the code. If you are interested in getting a preliminary version of this code, please contact me.

I did an earlier presentation on CG-rank at INFORMS 2003 Atlanta: CG-rank presentation (201K). Note that a few things in the presentation are no longer correct: the output of CG-rank is slightly different, and the license has changed.

License

CG-rank is open-source software. You may redistribute and/or modify it under the terms of either (your choice) the Common Public License (CPL) Version 1.0 or the GNU General Public License (GPL) Version 2 or later. See the file COPYING in the tarball.

Installation and Usage

Download the tarball below. Unpack it. Then see the files INSTALL and README for installation and usage instructions.

CG-rank was created in a GNU/Linux environment and has only been tested using GCC as a compiler. It is likely that it will compile relatively easily in other unix-like environments when using GCC.

If you are trying to build in other environments, such as Windows, or using other compilers, then you may have problems. Actually, if you have installed COIN-OR successfully, then you can probably get CG-rank to work as well. I may be willing to help resolve these problems; it depends on why you are using CG-rank (I'm certainly inclined to help researchers, who are probably the main people interested anyway) and how much time I have.

Download

cg-rank-0.2.tar.gz

I would appreciate hearing about your interest/use of CG-rank. I encourage you to send me an email at the address below, though there is no obligation to do so.

Feedback

Please direct all feedback, including questions, comments, and bug reports, to Brady Hunsaker: abhun-nospam-saker at speakeasy.net.