GCG

Branch-and-Price & Column Generation for Everyone

Paint my Problem

Paint my Problem

In this use case, we explain how you can explore your problem, finding out what structure GCG detected and exploring other alternatives that could fit better. We will also explain how the scoring of decompositions work.

Introduction

This is Carina. She has just finished her studies at the RWTH Aachen and completed her degree with a master's thesis at the Chair of Operations Research, where she picked up quite a lot of "tricks of the trade". Not wanting to move far, she wants to kick off her career as Vice Production Manager at a local factory for cookies and hard ginger bread with herbs and sugar crystals, an Aachen speciality, which are more or less neighbors to the Chair of Operations Research. As one of her first tasks, she has to plan how much to produce for the next weeks.
With her existing knowledge she dives into the options and quickly realizes that solving a mixed integer problem would be a sensible approach. Without further searching for a solver, she obviously wants to try GCG first. To start with, she has to formulate the problem.

Problem Definition

Sources: Lambertz GmbH & Co. KG, Aachen, CC BY-SA 3.0 de, 1, 2
For the producer of different biscuits, cookies and ginger bread, Carina wants to decrese stockholding periods and optimize production capacities to fulfill customer needs. The demands are estimated based on past data using a regression on different high-fidelity features and are thus assumed to be given. With the demand at hand, Carina first wants to try plan the next quarter plus a small margin, so she sets the number of time slots to 15. To start with, she wants to only plan for the 6 most popular items in their production, which total to a big portion of the whole sales.

The Single Level Capacitated Lot Sizing Problem

Carina quickly realized that this is an old-fashioned lot sizing problem. Thus, to formulate her problem, Carina uses a well known "text-book" model, a one by Billington et al., dating back to 1983 ([1]):

For more information on the variables and the program, please refer to [7] . As an expert, Carina is well aware of the decomposability of such a planning problem, Carina tries GCG, which will automatically detect structures in the problem and potentially solve it more efficiently using a Dantzig-Wolfe reformulation. She wants to solve this problem for 15 time steps and 6 items.
Since Carina's data is very similar to the data used by Trigeiro et al. ([7]), in the following, we will work with an instance from this paper, F36N (download).

Detection and Exploration

In this section, we will have a deeper look into the detection, also explaining some theoretical basics. For even more theory and the implementation, please visit the page The GCG Detection.

One of the steps GCG does to solve problems is the presolving. There, redundant inequalities are removed, bounds are strengthened through trivial presolving of the problem, etc. However, this removal of inequalities, even if they were "useless", might severely damage the structure of the problem, meaning that GCG's detectors will not be able to find a structure anymore. This is exactly what happens with Carina's instance (and many other instances).
After opening GCG, Carina reads in her test instance F36N:

GCG version 3.1.0 [GitHash: 65674b4e]
Copyright (C) 2010-2020 Operations Research, RWTH Aachen University
SCIP version 7.0.0 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: SoPlex 5.0.0] [GitHash: 0bc4dc9c6]
External codes:
SoPlex 5.0.0 Linear Programming Solver developed at Zuse Institute Berlin (soplex.zib.de) [GitHash: 6535a3c8]
CppAD 20180000.0 Algorithmic Differentiation of C++ algorithms developed by B. Bell (www.coin-or.org/CppAD)
ZLIB 1.2.11 General purpose compression library by J. Gailly and M. Adler (zlib.net)
============
original problem has 270 variables (0 bin, 90 int, 0 impl, 180 cont) and 195 constraints

To check if the chosen decomposition is sensible and suitable, Carina wants to use GCG's explore menu, which allows to go through decompositions and their details, visualize them and choose specific ones, before solving the problem. To enter the explore menu, Carina presolves the problem using presolve and detects using detect, which is the default behavior of GCG if one just types optimize.

GCG> presolve
presolving:
(round 1, fast) 20 del vars, 14 del conss, 0 add conss, 102 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
...
presolving (8 rounds: 8 fast, 3 medium, 3 exhaustive):
20 deleted vars, 14 deleted constraints, 0 added constraints, 188 tightened bounds, 0 added holes, 6 changed sides, 18 changed coefficients
806 implications, 2 cliques
presolved problem has 250 variables (87 bin, 0 int, 0 impl, 163 cont) and 181 constraints
87 constraints of type <varbound>
94 constraints of type <linear>
Presolving Time: 0.01
GCG> detect
starting detection
...
dec_consclass found 69 new partialdecs
dec_densemasterconss found 1 new partialdec
dec_neighborhoodmaster found 1 new partialdec
...
Detection Time: 0.11

The above log tells her that, during the presolving, some constraints were deleted and that, during detection, different decompositions were found. Next, Carina wants to look into the found decompositions:

GCG> exp
==================================================================================
Summary presolved original
--------- --------
detected 602 0
==================================================================================
nr id nbloc nmacon nlivar nmavar nstlva spfwh history pre nopcon nopvar sel
---- ---- ----- ------ ------ ------ ------ ----- ------- ---- ------ ------ ----
0 654 18 19 0 1 0 0.39 cC 1 0 0 0
1 638 15 18 0 0 0 0.39 cC 1 0 0 0
2 646 9 16 0 1 0 0.38 cC 1 0 0 0
3 630 6 15 0 0 0 0.38 cC 1 0 0 0
4 622 14 18 0 0 0 0.34 cC 1 0 0 0
5 615 12 70 0 62 0 0.28 cC 1 0 0 0
6 623 15 73 0 67 0 0.28 cC 1 0 0 0
7 647 14 71 0 65 0 0.28 cC 1 0 0 0
8 606 10 17 0 0 0 0.28 cC 1 0 0 0
9 655 17 74 0 70 0 0.28 cC 1 0 0 0
==================================================================================
Please enter command (or "h" for help) :

We see that in total, 602 decompositions were found. In the table, we can find information about each decomposition, most importantly the number of blocks (subproblems/pricing problems), the score of the decomposition used for ranking them (here, spfwh) and the history (which detectors were used to find that decomposition). For more information on the explore menu, please consider the manual The Explore Menu.

GCG always uses the decomposition with the highest score, thus the one with nr 0. To examine the one that will be used for solving, Carina types visualize 0, which will generate a gnuplot file, compile it and open the PDF using evince.

Decomposition 'number 0' of F62N with 18 blocks and 19 master constraints.

As one can see from the visualization and the table, this decomposition has 18 blocks and 19 master constraints. Carina tries to solve the instance, and it takes a while before GCG comes up with the optimal solution:

SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 172.85
Solving Nodes : 1664
Primal Bound : +3.53710000000000e+04 (180 solutions)
Dual Bound : +3.53710000000000e+04
Gap : 0.00 %

Waiting for up to 3 minutes for this (still very small) problem is no option, and thus she looks for different ways to solve it quicker.
She stumbles across some common ways to find a better decomposition using the explore menu, from easy to more advanced:

1. Visualize all decompositions and use the "most appealing" one
2. Inspect the number of blocks and master constraints
3. Changing the score that decompositions are rated by

Further ways to improve decomposition quality involve changing the detection process through its parameters, which is a method that is subject of the next use case, Tweaking the Detection.

Search for appealing Decompositions

There exist some cases, where experts can easily determine the "right" decomposition from simply seeing it. Visualizing it is very easy and can help users and experts to get an idea of what GCG sees in the problem.

Decomposition 'number 1' of F62N with 15 blocks and 18 master constraints.
Decomposition 'number 2' of F62N with 9 blocks and 16 master constraints.
Decomposition 'number 3' of F62N with 6 blocks and 15 master constraints.

Carina inspects the different decompositions and concludes that it might be possible that decomposition number 3 is superior to number 0, the one chosen by GCG, since the sizes of the blocks are more homogeneous, possibly resulting in pricing problem aggregation.

Inspecting the Numbers

GCG's detectors are built in such a way that they find regularities in the problem to exploit. These can be instance types, nonzeroes in the constraints or other factors. Thus, looking at the numbers and matching them with "the real ones" is often very promising. Carina again only focuses on the first 4 decompositions:

nr id nbloc nmacon nlivar nmavar nstlva ...
---- ---- ----- ------ ------ ------ ------ ...
0 654 18 19 0 1 0 ...
1 638 15 18 0 0 0 ...
2 646 9 16 0 1 0 ...
3 630 6 15 0 0 0 ...

While in this example, the three variable columns are not particularly interesting, the nbloc and nmacon columns are indeed. As Carina knows from her problem definition, she has 15 time steps and 6 items. Very easily, one can see how decomposition nr 3 is the one matching the numbers, and possibly the best matching one. Obviously, these numbers cannot be read and interpreted that easily for all problems, in particular not for ones with more than two dimensions per variable (here, the main variable is assembled out of a cartesian product set of the time steps and items).
To make this decomposition interpretable, Carina identifies that for each item (since they can be solved independently of each other), one sub-problem is created by GCG, if decomposition number 3 is chosen. To link the items with each other, constraints concerning the different time steps and the storing possibility are considered as master constraints, linking the pricing problems.

Changing the Score

Even though setting a different score is pretty simple and can be done by executing score <nr> from within the explore menu. After that, the respective score is set. A list of scores available can be found here.
After trying all the different scores, Carina observes that the numbers for all of the first three instances are very similar, making them hard to compare. In general, setting a sensible score other than the default one is no easy task and is mostly a thing of scientists. Thus, Carina decides to skip that step.

Bringing everything together

From the knowledge Carina has gained from the previous steps, she now decides to try a different decomposition, the one with number 3. To do that, she types select inside the explore menu, followed by the desired number, i.e. select 3. After that, she simply exits the explore menu with .. and optimizes the problem with optimize. Using decomposition number 3, she now achieves the following runtimes:

SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 8.60
Solving Nodes : 43
Primal Bound : +3.53710000000000e+04 (17 solutions)
Dual Bound : +3.53710000000000e+04
Gap : 0.00 %

With just a few easy steps, she achieved a very significant speedup. Now, she wants to preserve this exact decomposition to be able to use it again for different data.

Further Decomposition Exploration

To understand the decomposition even more, Carina also wants to inspect it. This can be done inside the explore menu, using inspect 3 in our case. She gets statistics about the decomposition and also about how GCG found it:

-- Detection and detectors --
PARTIALDECOMP stems from the presolved problem.
IDs of ancestor partialdecs: 1, 1, 50, 50
2 detectors worked on this partialdec:
1.: consclass
Detection time: 1.77536e-05
% newly assigned constraints: 0.0110497
% constraints the detector assigned to border: 0.0110497
% constraints the detector assigned to blocks: 0
% newly assigned variables: 0.004
% variables the detector assigned to border: 0.004
% variables the detector assigned to blocks: 0
New blocks: 0
Used conspartition: nonzeros
Pushed to master: 5, 9
2.: (finish) connectedbase
Detection time: 6.5e-05
% newly assigned constraints: 0.98895
% constraints the detector assigned to border: 0
% constraints the detector assigned to blocks: 0
% newly assigned variables: 0.996
% variables the detector assigned to border: 0
% variables the detector assigned to blocks: 0
New blocks: 1

This part of the log tells her that first, the consclass detector (see here for more information) classified the constraints according to classes, e.g. by their type (set partitioning constraint, knapsack constraint, etc.). Next, the connectedbase detector (see here for more information) assigns most of the constraints, yielding the decomposition we saw in the pictures above.

Export Decompositions

To reuse decompositions, one can easily export them as .dec files, which are not just readable for GCG but also for other solvers that apply decomposition to solve problems. To export the file, Carina simply types write selected . and answers the prompts to export the decomposition she previously selected in the explore menu to the current folder.

GCG> write selected
enter directory: .
enter extension: dec
All selected decompositions were written (directory: ., format: dec).

Now she sees a dec-file that she can easily reimport later on.

> ls *.dec
F36N-cC-630-6-dec.dec

Create Decomposition Report

To explore all decompositions in further detail, a decomposition report can be generated. This is done by simply typing

write reportdecompositions

and then entering a folder to write the LaTeX files to. Compilation is then done by executing

make -f makepdf_report_INSTANCENAME.make

where the result is a PDF with pages that look similar to this:

Disclaimer

The methods explained above are meant to show the capabilities of GCG and its explore menu and they don't necessarily apply in general. For further adjustments to the GCG detection, we refer to the next use case Tweaking the Detection.