How to get started

If you want to use GCG as a solver for your problem, you will find some starting information on this page.

You need a compiled GCG binary. The Install section will guide you through the correct steps. You will further need a problem you want to solve and you need to know what the structure information for the Dantzig-Wolfe reformulation does look like for your problem. GCG can read various file formats that SCIP can read, namely MPS, LP, CIP, and many more.

If you want to download the complete source code of the GCG, we recommend downloading the complete SCIP optimization suite as it will contain everything you will need in order to produce a working binary. The cutting stock instance TEST0055, which will serve as an example in this tutorial, can be found under gcg-[version]/check/instances/cs/TEST0055.lp.

Now start your binary, without any arguments. The usual place after compilation is bin/gcg. This opens the interactive shell, which should look somehow like this:

GCG version 1.0.0 [GitHash: v100]
Copyright (c) 2010-2012 Operations Research, RWTH Aachen University
                        Konrad-Zuse-Zentrum fuer Informationstechnik Berlin (ZIB)

SCIP version 3.0.0 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: SoPlex 1.6.0.7] [GitHash: 8330fdf]
Copyright (C) 2002-2017 Konrad-Zuse-Zentrum fuer Informationstechnik Berlin (ZIB)

External codes:
  Readline 6.2         GNU library for command line editing (gnu.org/s/readline)
  SoPlex 1.6.0.7       Linear Programming Solver developed at Zuse Institute Berlin (soplex.zib.de) [GitHash: 257a622]
  cppad-20120101.3     Algorithmic Differentiation of C++ algorithms developed by B. Bell (www.coin-or.org/CppAD)
  ZLIB 1.2.5           General purpose compression library by J. Gailly and M. Adler (zlib.net)

user parameter file <gcg.set> not found - using default parameters

GCG>

First of all "help" shows you a list of all available shell commands. Brackets indicate a submenu with further options.

GCG> help
 <change>              change the problem
 <display>             display information
 <set>                 load/save/change parameters
...
 read                  read a problem

Let's solve a problem with Dantzig-Wolfe reformulation... use "read <path/to/file>" to parse a problem file, "read <path/to/file>" to provide structure information, "optimize" to solve it and "display solution" to show the nonzero variables of the best found solution.

GCG> r check/instances/cs/TEST0055.lp

read problem <check/instances/cs/TEST0055.lp>
============

original problem has 220 variables (0 bin, 220 int, 0 impl, 0 cont) and 30 constraints
GCG> read check/instances/cs/TEST0055.dec

read problem <check/instances/cs/TEST0055.dec>
============

original problem has 220 variables (0 bin, 220 int, 0 impl, 0 cont) and 30 constraints
GCG> optimize

presolving:
presolving (0 rounds):
 0 deleted vars, 0 deleted constraints, 0 added constraints, 0 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
 0 implications, 0 cliques
presolved problem has 220 variables (20 bin, 200 int, 0 impl, 0 cont) and 30 constraints
     30 constraints of type <linear>
transformed objective value is always integral (scale: 1)
Presolving Time: 0.01
Chosen decomposition with 20 blocks of type arrowhead.


  time | node  | left  |LP iter|MLP iter|LP it/n| mem |mdpt |ovars|mvars|ocons|mcons|mcuts|confs|  dualbound   | primalbound  |  gap
   0.2s|     1 |     0 |     0 |      1 |     - |3876k|   0 | 220 |  10 |  31 |  31 |   0 |   0 | 0.000000e+00 |      --      |    Inf
Starting reduced cost pricing...
  time | node  | left  |LP iter|MLP iter|LP it/n| mem |mdpt |ovars|mvars|ocons|mcons|mcuts|confs|  dualbound   | primalbound  |  gap
s  6.1s|     1 |     0 |     0 |    375 |     - |6575k|   0 | 220 |1445 |  31 |  31 |   0 |   0 | 1.098400e+01 | 1.300000e+01 |  18.35%
X  6.2s|     1 |     0 |     0 |    375 |     - |6578k|   0 | 220 |1445 |  31 |  31 |   0 |   0 | 1.098400e+01 | 1.200000e+01 |   9.25%
   6.3s|     1 |     2 |     0 |    375 |     - |6582k|   0 | 220 |1445 |  31 |  31 |   0 |   0 | 1.098400e+01 | 1.200000e+01 |   9.25%
R  8.0s|    82 |     0 |     0 |   2432 |  25.4 |8115k|  27 | 220 |1778 |  31 |  31 |   0 |   0 | 1.098400e+01 | 1.100000e+01 |   0.15%

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 7.98
Solving Nodes      : 82
Primal Bound       : +1.10000000000000e+01 (8 solutions)
Dual Bound         : +1.10000000000000e+01
Gap                : 0.00 %

GCG> display solution

objective value:                                   11
x#3                                                 1    (obj:1)
x#4                                                 1    (obj:1)
x#5                                                 1    (obj:1)
...
y#9#10                                              3    (obj:0)
y#9#15                                             13    (obj:0)
...
y#10#16                                             1    (obj:0)

GCG>

This tells us the following: After "optimize", GCG would first go into presolving. Since we have specified a structure information for the original problem, GCG will currently disable presolving to not interfere with the decomposition. Each round of presolving will be displayed in a single line, with a short summary at the end. Here, there has been no round. Thus, it is not displayed and presolving is stopped. Afterwards, GCG will print out short information about the currently used decomposition.

Then, we see the actual solving process. The following lines indicate that new incumbent solutions were found by the primal heuristic with display character "s" in the original problem (master solutions are indicated by a '*' followed by the character); see, how the "primalbound" column changes from "--" (no feasible solution found so far) to 13 and goes down to 11 in the following lines. The second line indicates that reduced cost pricing is started. Before that, variables are added to the (initially empty) master problem by so-called Farkas pricing to render it feasible. Reduced cost pricing now adds variables with negative reduced costs to the master problem to improve its LP value. After 6.3 seconds, the root node processing is finished. We needed 375 master LP iterations (MLP iter) to solve the LP relaxation of the master problem to an near optimal value of 10.98, that is why the "dualbound" column changes from 0 to 10.98. We see that there are now two open nodes in the "left" column. From now on, we will see an output line every hundredth node or whenever a new incumbent is found (e.g. at node 82 in the above output). In our case, the "dualbound" at the root node was optimal (you could round it to the optimal integer dual bound), this is why it is not changing anymore. At one point, both primal bound and dualbound will be the same, and the solving process terminates, showing us some wrap-up information.

The exact performance varies amongst different architectures, operating systems, and so on. Do not be worried if your installation needs more or less time or nodes to solve.

We might want to have some more information now. Which were the primal heuristics that found the solutions? What plug-ins were called during the solutions process and how much time did they spend? How did the instance that we were solving look like? Information on certain plug-in types (e.g., primal heuristics, branching rules, separators) we get by "display <plug-in-type>", information on the solution process, we get by "display statistics", and "display problem" shows us the current instance.

GCG> display heuristics

 primal heuristic     c priority freq ofs  description
 ----------------     - -------- ---- ---  -----------
 gcgrins              N -1101000   20   5  relaxation induced neighborhood search by Danna, Rothberg, and Le Pape
 oneopt               b   -20000    1   0  1-opt heuristic which tries to improve setting of single integer variables
...
 simplerounding       r        0    1   0  simple and fast LP rounding heuristic
 gcgsimplerounding    r        0    1   0  simple and fast LP rounding heuristic on original variables
...
GCG> display statistics

Master Program statistics:
SCIP Status        : solving was interrupted [node limit reached]
Total Time         :       7.58
...
Pricers            :   ExecTime  SetupTime      Calls       Vars
  problem variables:       0.03          -         94        747
  gcg              :       7.19       0.00        119       1778
...
  simplerounding   :       0.01       0.00        122          0
...
Original Program statistics:
SCIP Status        : problem is solved [optimal solution found]
Total Time         :       8.00
...
Primal Heuristics  :   ExecTime  SetupTime      Calls      Found
...
  gcgrounding      :       0.00       0.00         82          1
  gcgshifting      :       0.00       0.00          7          5
...
Relaxators         :       Time      Calls
  gcg              :       7.75         83
...
GCG>

We see statistics for two different problems: The Dantzig-Wolfe master problem and the original problem. We see that gcgrounding and gcgshifting were the heuristics producing the solutions in the beginning. Rounding is called at every node, gcgshifting only at every tenth level of the tree. The statistics are quite comprehensive, thus, we just explain a few lines here. We get information for all types of plug-ins and for the overall solving process. Besides others, we see that in 82 calls of the gcgrounding heuristic, 1 solution was found and that the relaxator gcg got called 83 times and took a total of 7.75 seconds to execute. Further on top, we can see that pricing produced 1778 variables in 7.19 seconds.

To solve a problem a second time, we have to read it and start the optimization process again. This time, we let GCG discover the decomposition and display it.

Lets first see what detectors are available:

GCG> display detectors
 detector             priority char  description
 --------------       -------- ----  -----------
 connected                   0    b  Detector for classical and block diagonal problems

We only have the "connected" detector available which claims to detect classical set partitioning master problems. Let's see if that works:

GCG> read check/instances/cs/TEST0055.lp

read problem <check/instances/cs/TEST0055.lp>
============

original problem has 220 variables (0 bin, 220 int, 0 impl, 0 cont) and 30 constraints
GCG> detect
Starting detection
Detecting purely block diagonal structure: not found.
Detecting set partitioning master structure: found 20 blocks.
Chosen decomposition with 20 blocks of type bordered.
Detection was successful.

The "connected" detector has found 20 blocks. Let's inspect the decomposition:

GCG> display dec
PRESOLVED
0
NBLOCKS
20
BLOCK 1
b_capa_;1;
BLOCK 2
b_capa_;2;
...
MASTERCONSS
m_link_;1;
m_link_;2;
m_link_;3;
...

This tells us the following: The structure was detected from the unpresolved problem and contains 20 blocks. Next, the constraints per block (b_capa_;1; in block 1) are listed. Finally, all constraints in the master are listed. This DEC format is described in reader_dec.h .

Now, we can start playing around with parameters. We know that the root bound was optimal and we may want to branch early, e.g. we don't want to solve the master problem to optimality in all cases and explore branching decisions earlier. This is an advanced parameter, so we have to look into that section of the pricer.

GCG> set
  <branching>           change parameters for branching rules
  ...
  <pricing>             change parameters for pricing variables
  ...

GCG/set> pricing

  <masterpricer>        parameters for <masterpricer>
  abortfac              pricing is aborted, if fac * pricing/maxvars pricing candidates were found [2.0]
  delvars               should variables created at the current node be deleted when the node is solved in case they are not present in the LP anymore? [FALSE]
  delvarsroot           should variables created at the root node be deleted when the root is solved in case they are not present in the LP anymore? [FALSE]
  maxvars               maximal number of variables priced in per pricing round [100]
  maxvarsroot           maximal number of priced variables at the root node [2000]

GCG/set/pricing> masterpricer

  <advanced>            advanced parameters
  ...
   successfulsubmipsrel  part of the submips that are solved and lead to new variables before pricing round is aborted? (1.0 = solve all pricing MIPs) [1.0]

GCG/set/pricing/masterpricer> adv

  abortpricinggap       should pricing be aborted due to small gap between dual bound and RMP objective? [0.0]
  abortpricingint       should pricing be aborted due to integral objective function? [TRUE]
  useheurpricing        should pricing be performed heuristically before solving the MIPs to optimality? [FALSE]

GCG/set/pricing/masterpricer/advanced> abortpricinggap
current value: 0, new value [0,1]: 0.05
pricing/masterpricer/abortpricinggap = 0.05

GCG> o
  ...
  time | node  | left  |LP iter|MLP iter|LP it/n| mem |mdpt |ovars|mvars|ocons|mcons|mcuts|confs|  dualbound   | primalbound  |  gap
s  6.3s|     1 |     0 |     0 |    375 |     - |6586k|   0 | 220 |1445 |  31 |  31 |   0 |   0 | 1.098400e+01 | 1.300000e+01 |  18.35%
X  6.3s|     1 |     0 |     0 |    375 |     - |6589k|   0 | 220 |1445 |  31 |  31 |   0 |   0 | 1.098400e+01 | 1.200000e+01 |   9.25%
   6.5s|     1 |     2 |     0 |    375 |     - |6593k|   0 | 220 |1445 |  31 |  31 |   0 |   0 | 1.098400e+01 | 1.200000e+01 |   9.25%
*r 7.3s|    83 |     0 |     0 |   2443 |  25.2 |7281k|  26 | 220 |1550 |  31 |  31 |   0 |   0 | 1.100000e+01 | 1.100000e+01 |   0.00%

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 7.34
Solving Nodes      : 83
Primal Bound       : +1.10000000000000e+01 (6 solutions)
Dual Bound         : +1.10000000000000e+01
Gap                : 0.00 %

GCG>

Indeed, we gained an impressive improvement of 0.5s. Note that we generated less variables (1550 compared to 1778) but needed one more branching node. Note further that this time, the optimal solution was found in the master problem by the simple rounding heuristic, indicated by the "*r" characters.

We can navigate through the menus step-by-step and get a list of available options and submenus. Thus, we select "set" to change settings, "pricer" to change settings of pricers, "masterpricer" for that particular pricer. Then we see a list of parameters (and sometimes yet another submenu for advanced parameters), and set pricinggap to 0.05 in the advanced submenu. If we already know the path to a certain setting, we can directly type it (set pricing/masterpricer/abortpricinggap = 0.05). Note that we do not have to use the full names, but we may use short versions, as long as they are unique.

GCG can also write information to files. E.g., we could store the incumbent solution to a file, or output the problem instance in another file format (the LP format is much more human readable than the MPS format, for example). We can also write out the currently used decomposition by saving the problem as a decomposition format (DEC, BLK or REF).

GCG> write sol TEST0055.sol

written solution information to file <TEST0055.sol>

GCG> write prob TEST0055.dec
written original problem to file <TEST0055.dec>
GCG> q
...

We hope this tutorial gave you an overview of what is possible using the SCIP interactive shell within GCG. Please also read our Frequently Asked Questions (FAQ).