GCG
Generic column generation
Generic column generation
GCG is a generic branch-cut-and-price solver for mixed integer programs. It is based on the branch-and-cut-and-price framework SCIP and is also part of the SCIP Optimization Suite.
After the standard presolving process of SCIP, GCG performs a Dantzig-Wolfe decomposition of the problem to obtain an extended formulation of the problem. The decomposition is based on a structure either provided by the user or automatically detected by one of the structure detectors included in GCG .
During the solving process, GCG manages two SCIP instances, one holding the original problem, the other one representing the reformulated problem. The original instance coordinates the solving process while the other one builds the tree in the same way, transfers branching decisions and bound changes from the original problem and solves the LP relaxation of the extended formulation via column generation.
GCG is developed jointly by RWTH Aachen and Zuse-Institute Berlin and has more than 50,000 lines of C code.
An outline of GCG and its algorithmic approach can be found in
02/Jul/2018 | A major GCG 3.0.0 release is available together with the SCIP optimization Suite 6.0.0. See the CHANGELOG and the Release notes for more information. |
09/Mar/2017 | A small GCG 2.1.2 bugfix release is available together with the SCIP optimization Suite 4.0.0. See the CHANGELOG and the Release notes for more information. |
29/Feb/2016 | A small GCG 2.1.1 bugfix release is available together with the SCIP optimization Suite 3.2.1. See the CHANGELOG and the Release notes for more information. |
01/Jul/2015 | We released the minor version GCG 2.1.0 together with the SCIP optimization Suite 3.2.0. See the CHANGELOG and the Release notes for more information. |
18/Dec/2014 | A small GCG 2.0.1 bugfix release is available together with the SCIP optimization Suite 3.1.1. |
26/Feb/2014 | A new major version GCG 2.0.0 is available together with the SCIP optimization Suite 3.1.0 and plenty of new features! |
16/Oct/2013 | A small GCG 1.1.1 bugfix release version is available together with the SCIP optimization Suite 3.0.2. |
04/Jan/2013 | We released the minor version GCG 1.1.0 together with the SCIP optimization Suite 3.0.1. |
01/Aug/2012 | We released the first version of GCG 1.0.0 together with the SCIP optimization Suite 3.0.0. |
GCG is released under the LGPL. If you use GCG in a publication, please reference the following article:
Experiments with a Generic Dantzig-Wolfe Decomposition for Integer Programs, Gerald Gamrath and Marco E. Lübbecke
In P.Festa (Ed.), Symposium on Experimental Algorithms (SEA 2010), LNCS, 6049, pp. 239-252, 2010, Springer, Berlin. DOI: 10.1007/978-3-642-13193-6_21
GCG has the following features:
GCG is written in C and C++. It should compile with any recent and ANSI compliant C and C++ compiler. We have tested the compilation with the following compilers:
on 32- and 64-bit versions of
Here is a list of known bugs in the current version:
GCG has more than 50,000 lines of source code and is definitely not bug free.
If you find a bug, please write an email to gcg-bugs-listor.rwth-aachen.de .
Marco Lübbecke | Project initiator and head |
Michael Bastubbe | Structure detection, main developer |
Gerald Gamrath | Original and main developer |
Christian Puchert | Primal heuristics, main developer |
Jonas Witt | Cutting planes, main developer |
Martin Bergner | Structure detection, former main developer |
Björn Dählmann | Former student assistant, structure detection |
Hanna Franzen | Student assistant, structure detection |
Alexander Groß | Former student assistant, statistics |
Hannah Hechenrieder | Former student assistant, structure detection |
Julius Hense | Former student assistant, structure detection |
Lukas Kirchhart | Former student assistant, documentation |
Henri Lotze | Former student assistant, cliquer pricing solver |
Mathias Luers | Staircase structure detection |
Tobias Oelschlägel | Former student assistant, set covering heuristic |
Marc Peiter | Former student assistant, testing |
Daniel Peters | Former student assistant, detection of similar pricing problems |
Niklas Rieken | Student assistant, statistics |
Marcel Schmickerath | Former student assistant, generic branching |
Annika Thome | Graph library methods |
If you know about further projects or papers that use GCG, please let us know.
The files you can download here come without any warranty. Use at your own risk!
You can either download GCG alone or the SCIP Optimization Suite (recommended), a complete source code bundle of SCIP, SoPlex, ZIMPL, GCG, and UG with an easy-to-use Makefile.
Due to licensing issues, we can not offer precompiled binaries. You can download the source code here:
or complete in the SCIP Optimization Suite.