### Table of Contents

# Paint my Problem

In this use case, we explain how you can explore your problem, finding out

what structure GCG detectedandexploring other alternativesthat 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.