Generic column generation
Generic column generation
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.
An outline of GCG and its algorithmic approach can be found in
|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-bugsor.rwth-aachen.de .
|Marco Lübbecke||Project initiator and head|
|Martin Bergner||Structure detection, former main developer|
|Gerald Gamrath||Original and main developer|
|Christian Puchert||Primal heuristics, main developer|
|Jonas Witt||Cutting planes, main developer|
|Michael Bastubbe||Graph library methods|
|Björn Dählmann||Student assistant, structure detection|
|Hanna Franzen||Student assistant, structure detection|
|Alexander Groß||Student assistant, statistics|
|Lukas Kirchhart||Student assistant, documentation|
|Tobias Oelschlägel||Student assistant, set covering heuristic|
|Marc Peiter||Student assistant, testing|
|Daniel Peters||Student assistant, detection of similar pricing problems|
|Marcel Schmickerath||Student assistant, generic branching|
|Annika Thome||Graph library methods|
If you know about further projects or papers that use GCG, please let us know.
GCG is developed in cooperation with
|Konrad-Zuse-Zentrum für Informationstechnik Berlin|
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.