GCG is a generic solver for Dantzig-Wolfe reformulation using branch-cut-and-price. It contains all code to serve as a standalone solver for structured mixed integer programs (MIPs) and the accompanying structure information. This FAQ contains common questions as well as starting information and known bugs.
GCG can solve all problems for which a structure for Dantzig-Wolfe reformulation is known. The structure is either automatically detected by GCG (see next question) or supplied as a decomposition file (see filereaders).
GCG contains several detectors to find a block diagonal structures in
the constraint matrix, pure ones as well as such with a
border. Additionally, some detectors are able to detect staircase
structures where no linking constraints are present and linking variables
only occur between two consecutive blocks.
With applications such as bin packing, capacitated p-median and generalized assignment problems in mind, we furthermore included a detector that only assigns set partitioning and set covering constraints to the master problem.
While several detectors are only experimental, others need external software. Some detectors rely on hMETIS and only work under Unix based systems. To use them, you must either install hMETIS from the package sources (if available there) or download it and put the executable in a directory contained in the PATH environment variable. The Isomorphism detector needs Bliss (see here).
Currently GCG reads three different decomposition structure information:
As GCG uses several presolving methods from SCIP, the transformed problem
(see also SCIP FAQ) may change significantly from the original
problem. Variables or constraints may be deleted or added which renders
the current decomposition invalid or unsuitable in some cases. GCG does
some basic sanity checks, however, it doesn't handle all problems and may
crash if the decomposition is read at the wrong time (e.g. a
decomposition found after presolving is read before the problem is
Use only non presolved decompositions and disable presolving if you are in doubt!
If GCG can not detect whether your decomposition is for the presolved or the original problem, it cannot guard you against errors. See the previous question for more information.
In its current version, SCIP will finish the current node when pressing CTRL-C. This is a problem if the master problem is not completely finished solving. The current node will be marked as finished and two branching children are created. Depending on when you press CTRL-C, this may and will lead to different solving processes. If an optimal solution is found, they will be the same in all runs, however, it might take a substantially different amount of time to do so.
Detecting whether (some) pricing problems can be aggregated is done using
Bliss, an external
tool for computing automorphism groups of graphs. After a decomposition has been
selected, we check for each pair of pricing problems if they are identical
(and their variables have the same coefficients in the same master constraints)
by creating an auxiliary graph and trying to find a suitable automorphism
using Bliss. Identical pricing problems are then aggregated.
See the installation information
for an instruction on how to include bliss.
If Bliss is not included, aggregation in GCG is done very simple. If the same variables appear in the same order with the same coefficients in the same constraints for all pricing problems (and with the same coefficients in the master constraints), GCG will detect that and aggregate the pricing problems.