How to read the CBC (Pulp, python-mip) solver log

I tried to summarize how to read the log of the CBC (COIN-OR Brand-and-Cut) solver that can be operated freely from Pulp [^ 1] and python-mip [^ 2]. (I have compiled it as a personal memo, so please point out any mistakes.)

The content is almost a translation of the following pdf.

• CBC : COIN-OR Branch-and-Cut (A Short Guide to the CBC Command Line Interface)
  http://www.decom.ufop.br/haroldo/files/cbcCommandLine.pdf

Introduction

In the above pdf, message 7 is explained using the log when calculating the benchmark of the Set Partitioning problem called air03. Message 7 and later are explained using `air04'.

http://miplib2017.zib.de/instance_details_air03.html http://miplib2017.zib.de/instance_details_air04.html

You can get the mps file from the link above. You can use read in python-mip to read and calculate the problem. (Pulp doesn't have a read function ... although it does have a write.)

How to read the log

Messages 1-3

Message 1

Continuous objective value is 338864 - 0.05 seconds

The value (cost) and calculation time of the objective term when solving the linear relaxation solution of the model are displayed. In this example, a linear relaxation solution with a cost of 338864 is obtained in 0.05 seconds. This value is the upper and lower bound of the original problem. (In the case of minimization, it is the lower bound, and in the case of maximization, it is the upper bound. From now on, we will consider the minimization problem.) Since no special operation is performed, it is the lowest estimated lower world.

Message 2

Cgl0004I processed model has 120 rows, 8456 columns (8456 integer) and 71651 elements

The line marked Cgl is ** preprocessed **. Cgl seems to be an abbreviation for Cut Generation Library [^ 3].

The constraints (rows), variables (columns), and number of nonzero elements (elements) after reduction in preprocessing are displayed in the last row. Preprocessing reduces the size of the problem as shown below.

It seems that the smaller the size of the problem in the preprocessing, the easier it is for the MIP solver to solve.

Message 3

Cbc0038I Pass 1: suminf. 8.33333 (22) obj.  341524 iterations 106
Cbc0038I Pass 2: suminf. 8.33333 (22) obj.  341524 iterations 3
Cbc0038I Pass 3: suminf. 8.33333 (22) obj.  341524 iterations 70
Cbc0038I Pass 4: suminf. 7.20000 (20) obj.  342390 iterations 75
Cbc0038I Pass 5: suminf. 1.50000 (3)  obj.  343697 iterations 45
Cbc0038I Pass 6: suminf. 1.50000 (3)  obj.  343697 iterations 55
       ...
Cbc0038I Pass 12: suminf. 0.00000 (0) obj.  362176 iterations 144
Cbc0038I Solution found of 362176

It means that Cbc0038I has started. In Cbc0038I, the initial solution (provisional solution) that is a feasible solution is searched for using a method called ** Feasibility Pump (M. Fischetti, Glover, & Lodi, 2005) [^ 4], [^ 5] **. Seems to be doing. (Is I an abbreviation for Initial?) After the 12 Passes are completed, the message Cbc0038I Solution found of 362176 is displayed, indicating that a provisional solution with a cost of 362176 was obtained. Since the lower bound displayed in message 1 was 338864, we can see that there is an optimal solution (exact solution) in at least the range of[338864, 362176]. The smaller the gap between the cost of the provisional solution and the lower bound, the better the CBC's performance.

Messages 4 ~ 6

Message 4

Cbc0012I Integer solution of 340160 found by DiveCoefficient after 14 iterations and 0 n odes (0.97 seconds)

The result of preprocessing called ** DiveCoefficient [^ 5], [^ 6] ** is displayed. (I don't know the details.) As a result, the provisional solution has been further updated to make the gap a section of [338864, 340160].

Message 5

Cbc0013I At root node, 5 cuts changed objective from 338864.25 to 340160 in 2 passes

It seems that the cut algorithm is being executed. In particular, in order to improve the upper and lower bounds of the ** duality problem **, it seems that he is trying some cuts that remove the fractional values of the obtained mitigation solution. It seems that 5 types of cuts were performed in this example. Details are displayed at the bottom of the log.

Cbc0014I Cut generator 0 (Probing) - 0 row cuts average 0.0 elements, 160 column cuts (160 active) in 0.840 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 4 row cuts average 1257.2 elements, 0 column cuts (3 active) in 0.020 seconds - new frequency is -100
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.020 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 10 row cuts average 3.7 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is 1
Cbc0014I Cut generator 6 (TwoMirCuts) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.030 seconds - new frequency is -100

The 0th, 1st and 3rd cuts seem to be sufficient for this problem. (You can see that Gomory Cut [^ 7] and Clique Cut are especially effective.) It was determined that the upper bound of the dual problem is 340160. Since the cost of the provisional solution is also 340160, it can be seen that it is the optimum solution.

Message 6

Result - Finished objective 340160 after 0 nodes and 11 iterations - took 4.75 seconds (total time 5.06)
Total time 5.14

The final cost value and calculation time are displayed. For this problem, the root node has a sufficiently good executable solution and the upper bound of the dual problem, so no further pruning of the branch cutting method is performed.

Messages 7, 8

These messages are the logs you see when you calculate the more difficult problem (air04). It seems that this search is done before the branch-and-bound method in air04. The number of nodes searched by the tree structure search of the molecular limitation method and the number of nodes that have not been searched yet are displayed. Each time a new integer is obtained, information about its cost and the method used is displayed. (Message 8)

The above is how to read the log. For reference, the log when calculating air03 and air04 using python-mip is uploaded below. https://github.com/Noriaki416/Qiita/tree/master/CBC_log

air0 # _cbc_log.txt will be the log.

tuning

By reading the logs, you can see which process is the bottleneck in solving the problem. You should be able to improve the solution performance by identifying the cause and tuning. Detailed tuning parameters are described after p6 of the pdf at the beginning.

When tuning using Pulp, it seems that you can specify it with options. It is explained in detail in the blog below.

https://inarizuuuushi.hatenablog.com/entry/2019/03/07/090000

options allows you to set other CBC options. For example, to use the maxsol option, set options = ['maxsol 1']. The maxsol option allows you to specify how many tentative solutions are found before the calculation ends. If you want one executable solution, even if it is not the optimal solution, you can use maxsol 1 to find it in a faster time. I can do it.

Parameters other than maxsol are also described on the GAMS [^ 8] site. It may be interesting to see the difference when playing with various things.

That's it. If you have any suggestions, please do not hesitate to contact us.