Frequently Asked Questions (FAQ)

Sections

General Questions about GCG

What is GCG?

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.

What MIPs can GCG solve?

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).

What are the detected structures?

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.

Why are some detectors switch off by default?

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).

Decomposition file related questions

Which filereaders can read decompositions?

Currently GCG reads three different decomposition structure information:

Why is presolving important for the decomposition?

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 presolved).
Use only non presolved decompositions and disable presolving if you are in doubt!

After reading the decomposition file, GCG tells me that the behaviour is undefined.

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.

Miscellaneous

Why is CTRL-C unsafe to use?

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.

How does aggregation work in GCG?

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.