GCG
Branch-and-Price & Column Generation for Everyone
Branch-and-Price & Column Generation for Everyone
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.
|
|
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.
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 ...
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.
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.
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.
| Marco Lübbecke | Project initiator, strategic coodination |
| 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 |
| 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 |
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.
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.
If you find a bug, please write an email to gcg-bugs@or.rwth-aachen.de.
GCG is developed in cooperation with
|
Konrad-Zuse-Zentrum für Informationstechnik Berlin |
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