Table of Contents
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
:
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
.
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:
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.
Visualizing with 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
.
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:
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:
- Visualize all decompositions and use the "most appealing" one
- Inspect the number of blocks and master constraints
- 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.
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:
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:
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:
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.
Now she sees a dec
-file that she can easily reimport later on.
Create Decomposition Report
To explore all decompositions in further detail, a decomposition report can be generated. This is done by simply typing
and then entering a folder to write the LaTeX files to. Compilation is then done by executing
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.