General Questions about GCG

What is GCG?

GCG is a branch-price-and-cut solver that also enables easy inclusion of own methods. With its different techniques such as Dantzig-Wolfe and Benders decomposition, GCG is able to solve some instances much quicker than other solvers, so it is always worth to let GCG solve your instance.
When should I use GCG?
You should use GCG if you want to...
- solve a problem that might have a structure in it (whether known or unknown) much faster (see Why use GCG?)
- find out about how your problem is structured (see Explore Menu)
- implement your own rules, heuristics and methods without having to implement branch-and-price (see Example Projects)
How is GCG licensed?

Just like for SCIP, as long as you use it for academic, non-commercial purposes, you do not need to buy any license. This will not change. For the other cases, check the explanation of the ZIB academic license and always feel free to ask us.
How do I get started?

The installation page will not only explain how you can get GCG up and running but also hint to next steps. For most, it is sensible to start with the Getting Started Guide.

Reading your problem and configuring GCG

How do I create a file out of my pen-and-paper program?

You will first have to create a program file that can be read by GCG. We offer readers for multiple input file formats, along which are the most frequently used ones (.lp, .mps). Additionally, a ZIMPL interface is already present and a GAMS interface is in development. With all these possible file formats, you can choose which one to go with. For new users, we recommend using ZIMPL to convert your paper-and-pen-program to a computer file. After you obtained the required file, get started with our guide and read it.
How do I create my own settings file?

A settings file should be located in the settings folder inside the root directory. The most common way to generate a settings file is through the set diffsave command inside GCG that exports a .set-file with all parameters that you changed.\n Otherwise, you can also define a settings file by yourself. In each line, a parameter can be set. This parameter is of the same form that it is in GCG, for example "detection/detectors/connected/enabled". Often, these parameters are bools, so turning on the connected detector could be done by "detection/detectors/connected/enabled = TRUE". All possible parameters of GCG's current version can be found here. Note that the #-symbol will start comments.
How can I create solution files from an out file?

If you already have an out file and are confident that the results in it are correct, you can make a .solu file out of it by setting the flag writesolufile to 1 in the file check/check.awk and calling the script check/evalcheck.sh on your .out-file. This will generate a solution file called new_solufile.solu inside the check/ directory.

For manual generation of the .solu file, you can check out the syntax definition here.

Presolving

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!

Structure Detection

What decomposition files can be read?
Currently, GCG reads three different decomposition structure information file types:
- .dec
- .blk
- .ref
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.
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.
Why are some detectors switch off by default?

While several detectors are only experimental, others need external software. These detectors rely on additional packages (and only work under Unix based systems). To use the Hypergraph Partitioning Detectors, 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. Additionally, the Isomorphism detector needs Bliss. For information on how to install the external software, please consult the Manual Installation Guide.
How do I create or export my own decomposition file?

Generally, we recommend to try to make GCG detect your desired decomposition by using the settings instead of creating it by hand. For example, you could look up which detector decomposes your instance in the way you want it to be and then only activate this detector. To find out which detector you need, look up which structure each detector finds here. Then, create your own settings file, where only this detector is enabled as described here. After detecting, perform a write alldecompositions to export all decompositions.

If you still want to write your .dec-file by hand, you can find the required syntax here. A more human readable example and information how to use the .dec-file can be found in How to create and use your own decomposition.
How do I generate decomposition visualizations?

Just like the picture on the GCG landing page, you can export images of how GCG decomposed your program. This can be done in the Explore Menu.

To find out which decomposition stems from what other, GCG can also generate a decomposition "family tree". This is done with "write familytree".

To visualize the coefficient matrix of the original coefficient matrix, read the problem in and use write matrix.

Branch-and-Price

Why are not all pricers used by default?

Just like with the detectors, some pricing solvers require additional software. Currently, only the Cliquer pricing solver requires external code. Apart from that, all pricing solvers are activated by default, though with different priorities (see here for more information).

Visualization Suite

What is the Visualization Suite?

The GCG Visualization Suite offers different bash and Python scripts that allow to unveil runtime behavior. The process of solving instances can be visualized on granular level, in aggregated form or compared to other solving runs. The scripts can sometimes be harder to generate and interpret, since they partly assume expert knowledge, but are thus very powerful if used correctly. An in-depth guide to all scripts can be found here. As an easy entry to the manual visualization generation, we recommend using the Jupyter-based Visualization Notebook (see below).

For most users, however, the most important features are the reporting functionalities as described here. One can create testset reports with aggregated and instance-wise visualizations and comparison reports with comparing visualizations.
What is the Visualization Notebook?

The Visualization Notebook imports parts of the visualization suite and allows for easy access to them. It gives a structure that one can follow when conducting experiments. Note that it does not offer functionality to use GCG through its Python interface.
How do I generate runtime visualizations?

Apart from the decomposition visualizations (as described in "How do I generate decomposition visualizations?"), GCG also comes with some python scripts that allow to make graphics showing the pricing process, time distribution, bounds development and more. A guide on how to use those scripts can be found here

Interfaces

How do I use the GAMS interface?

For the GAMS interface to run with GCG, you have to make sure that the dependencies were compiled with SHARED=true and READLINE=false. Apart from that, a detailed guide is given here.
How do I use the Python interface?

To use the Python interface, please consult the corresponding guide.

Possible errors and caveats

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.
After reading the decomposition file, GCG tells me that the behavior is undefined.

If GCG can not detect whether your decomposition is for the presolved or the original problem, it cannot guard you against errors.