GCG

Generic column generation

About

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.


What Is GCG?

An outline of GCG and its algorithmic approach can be found in

News

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.

License

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

Features

GCG has the following features:

  • It is black box solver using a Dantzig-Wolfe reformulation (DWR) to solve arbitrary MIPs.
  • It is a framework for implementing column generation algorithms
  • It detects hidden or apparent structures in the constraint matrix in order to apply DWR. Among others, it detects
    • Staircase structures
    • Set partitioning master structures
    • Subproblems that can be aggregated in the Dantzig-Wolfe reformulation
    • With the additional tool hmetis it can enforce a structure suitable for DWR in arbitrary MIPs
  • It has branching rules for automatic branching on any problem.
  • Stabilization by dual value smoothing
  • A large number of primal heuristics both in the original and the reformulated space

Platforms

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:

  • GNU compiler collection
  • LLVM Clang
  • Intel Studio compiler

on 32- and 64-bit versions of

  • Linux
  • Mac
  • Windows

Bugs

Known Bugs

Here is a list of known bugs in the current version:

  • There might be problems branching on discretized and aggregated problems. If you encounter such an issue, try to turn off either aggregation or discretization.

Reporting Bugs

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-listklammeraffeor.rwth-aachen.de .

Developers

Project head

Marco Lübbecke Project initiator and head

Main developers

Michael Bastubbe Structure detection, main developer
Gerald Gamrath Original and main developer
Christian Puchert Primal heuristics, main developer
Jonas Witt Cutting planes, main developer

Former developers

Martin Bergner Structure detection, former main developer

Contributors

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

Related Work

If you know about further projects or papers that use GCG, please let us know.

Cooperation

GCG is developed in cooperation with

Konrad-Zuse-Zentrum für Informationstechnik Berlin ZIB Logo

Download

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.