Scippy

GCG

Branch-and-Price & Column Generation for Everyone

Welcome!

GCG is a generic decomposition solver for mixed-integer programs (MIPs). It automatically performs a Dantzig-Wolfe reformulation and runs a full-fledged branch-price-and-cut algorithm to solve it to optimality. Alternatively, GCG is able to automatically apply a Benders decomposition. No user interaction is necessary, thus GCG provides decomposition-based MIP solving technology to everyone. When used as a framework, GCG allows for easy modification/extension of algorithmic behavior and components. As such, it should reduce researchers' coding efforts, facilitate standardized experiments, and increase comparability and reproducibility of computational experiments using decomposition methods.

before detection
Fig.1: Non-zero entries in original matrix
after detection
Fig. 2: Non-zero entries after re-arrangement

An essential feature of GCG is its ability to detect decomposable model structure in MIPs. The figures above show an example MIP coefficient matrix, before and after structure detection.

About GCG

GCG is a generic decomposition solver for mixed integer linear programs that extends the SCIP (Solving Constraint Integer Programs) framework. It finds structures in models that can be used to apply a Dantzig-Wolfe reformulation or Benders decomposition. Decompositions can also be user-given, and explored and evaluated manually. For a Dantzig-Wolfe reformulated model, a branch-price-and-cut algorithm solves the problem, which features primal heuristics, generic and specific pricing solvers, branching rules, dual variable stabilization, cutting planes, etc. Like SCIP, also GCG can be used as a framework and extended to suit one's needs.

Click for a detailed list of GCG's features ...

Download

We recommend you to download the SCIP Optimization Suite, a complete source code bundle of SCIP, SoPlex, ZIMPL, GCG, and UG with an easy-to-use Makefile.
However, you can also download the GCG source code alone.

Installation, Guides, and Documentation

Apart from this landing page, we also have a version-dependent documentation. In this documentation, we offer installation instructions, a "getting started" guide, explanations for all features of GCG, and explanations of components of GCG along with use-cases and example projects.

If you are looking for the documentation of GCG's Python interface (PyGCGOpt): you can find it here.

Related Work

Here is a list of papers that use GCG or describe parts of its functionality.
If you know about further projects or papers, please drop us a mail under gcg@or.rwth-aachen.de.

Team Members

Project head

Marco Lübbecke Project initiator, strategic coodination

Main developers

Michael Bastubbe Structure detection
Martin Bergner Structure detection
Gerald Gamrath Original concept and development
Stephen J. Maher Benders decomposition
Erik Mühmer Recursive GCG, structure detection
Christian Puchert Primal heuristics, pricing loop
Jonas Witt Cutting planes, strIPlib

Contributors

Björn Dählmann Structure detection
Tim Donkiewicz Documentation, visualization suite, strIPlib
Simon Feiden Chvátal-Gomory master cuts
Hanna Franzen Structure detection, visualization, refactoring
Oliver Gaul Strong branching in branch-and-price
Alexander Groß Statistics
Alexander Helber Frontend & backend strIPlib
Julius Hense Cons/vars classification
Lukas Kirchhart Documentation, strIPlib
Stefanie Koß GAMS/GCG interface
Henri Lotze CLIQUER stable set pricer
Matthias Luers Staircase detectors
William Ma Frontend strIPlib, refactoring
Adam Marciniak Frontend strIPlib
Friederike Menge Staircase detectors
Tobias Oelschlägel Set covering heuristic
Marc Peiter Testing
Igor Pesic DBSCAN clustering detector
Daniel Peters Detection of similar pricing problems
Maximilian Peters Continuous integration, unit testing
Niklas Rieken strIPlib instance curation
Steffan Schlein Python interface (PyGCGOpt)
Marcel Schmickerath Generic (Vanderbeck) branching
Vladimir Stadnichuk Chvátal-Gomory master cuts
Annika Thome Graph library methods
Matthias Walter CMake integration

More Information

Contact

For general information or questions about GCG, there are different options to get in touch with us.
Trouble compiling GCG from source? Please check the installation guide before sending an email.

Mailing List

All GCG developers are subscribed to the SCIP mailing list, thus it is a good idea to subscribe to it if you are actively working with GCG. It can be accessed via the SCIP mailing list page. After subscribing, you can write to the list via scip@zib.de.

Stack Overflow

We are also watching the GCG tag on Stack Overflow and will answer your questions there. Note that we will not answer faster only because you posted the same question both to stack overflow and the mailing list.

Reporting Bugs

If you find a bug, please write an email to gcg-bugs@or.rwth-aachen.de.

Cooperation

GCG is developed in cooperation with

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

License and Citing

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