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.

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

fig1.png

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.

Constraints variable Non-zero element
Before pretreatment 823 8904 72965
After pretreatment 120 8456 71651

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

fig2.png

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

fig3.png

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.

Recommended Posts

How to read the CBC (Pulp, python-mip) solver log
How to read the SNLI dataset
How to read PyPI
How to read JSON
Read the Python-Markdown source: How to create a parser
How to use the Rubik's Cube solver library "kociemba"
How to use the generator
How to use the decorator
How to increase the axis
How to start the program
How to switch the configuration file to be read by Python
How to log in automatically like 1Password from the CLI
How to use the zip function
How to change the log level of Azure SDK for Python
How to use the optparse module
How to make a command to read the configuration file with pyramid
How to get the Python version
[Python] How to import the library
How to use the ConfigParser module
How to log in to Docker + NGINX
[Image recognition] How to read the result of automatic annotation with VoTT
How to use the Spark ML pipeline
How to read pydoc on python interpreter
How to solve the bin packing problem
How to set the server time to Japanese time
How to manually update the AMP cache
[Linux] How to use the echo command
Until you can read the error log
How to use the Linux grep command
How to get colored output to the console
How to operate Linux from the console
How to access the Datastore from the outside
How to use the IPython debugger (ipdb)
How to read CSV files in Pandas
How to read problem data with paiza
How to read all the classes contained in * .py in the directory specified by Python
The first step to log analysis (how to format and put log data in Pandas)
How to assign multiple values to the Matplotlib colorbar
How to calculate the volatility of a brand
How to use the C library in Python
How to read a CSV file with Python 2/3
Log in to the remote server with SSH
How to specify the launch browser for JupyterLab 3.0.0
How to use MkDocs for the first time
How to specify the NIC to scan with amazon-dash
How to delete log with Docker, not to collect log
Setting to output the log of cron execution
[Python] How to change the date format (display format)
The inaccuracy of Tensorflow was due to log (0)
[Python] How to read excel file with pandas
[Python] How to read data from CIFAR-10 and CIFAR-100
How to try the friends-of-friends algorithm with pyfof
How to use the graph drawing library Bokeh
How to print debug messages to the Django console
How to use the Google Cloud Translation API
How to operate Linux from the outside Procedure
How to use the NHK program guide API
[Algorithm x Python] How to use the list
How to erase the characters output by Python
How to measure line speed from the terminal
How to get the files in the [Python] folder