Comment lire le journal du solveur CBC (Pulp, python-mip)

J'ai essayé de résumer comment lire le journal du solveur CBC (COIN-OR Brand-and-Cut) qui peut être utilisé librement à partir de Pulp [^ 1] et python-mip [^ 2]. (Je l'ai compilé sous forme de mémo personnel, veuillez donc signaler toute erreur.)

Le contenu est presque une traduction du pdf suivant.

• 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

Dans le pdf ci-dessus, le message 7 est expliqué en utilisant le journal lors du calcul du benchmark du problème Set Partitioning appelé air03. Les messages 7 et suivants sont expliqués à l'aide de «air04».

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

Vous pouvez obtenir le fichier mps à partir du lien ci-dessus. Vous pouvez utiliser read dans python-mip pour lire et calculer le problème. (Pulp n'a pas de fonction read ... bien qu'elle ait une write.)

Comment lire le journal

Messages 1 à 3

Message 1

Continuous objective value is 338864 - 0.05 seconds

La valeur (coût) et le temps de calcul du terme objectif lors de la résolution de la solution de relaxation linéaire du modèle sont affichés. Dans cet exemple, une solution de relaxation linéaire avec un coût de "338864" est obtenue en "0,05" seconde. Cette valeur correspond aux limites supérieure et inférieure du problème d'origine. (Dans le cas de la minimisation, c'est la borne inférieure, et dans le cas de la maximisation, c'est la borne supérieure. À partir de maintenant, nous allons considérer le problème de la minimisation.) Puisqu'aucune opération spéciale n'est effectuée, il s'agit du monde inférieur estimé le plus bas.

Message 2

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

La ligne marquée «Cgl» est ** prétraitée **. Cgl semble être une abréviation de Cut Generation Library [^ 3].

Les contraintes (lignes), les variables ( colonnes) et le nombre d'éléments non nuls (éléments) après réduction du prétraitement sont affichés dans la dernière ligne. Le prétraitement réduit la taille du problème comme indiqué ci-dessous.

Il semble que plus la taille du problème dans le prétraitement est petite, plus il est facile pour le solveur MIP de le résoudre.

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

Cela signifie que Cbc0038I a démarré. Dans Cbc0038I, la solution initiale (solution provisoire) qui devient une solution réalisable est recherchée en utilisant une méthode appelée ** Feasibility Pump (M. Fischetti, Glover, & Lodi, 2005) [^ 4], [^ 5] **. Semble faire. (Est-ce que «I» est une abréviation pour Initial?) Une fois les 12 passes terminées, le message "Solution Cbc0038I trouvée de 362176" s'affiche, indiquant qu'une solution provisoire avec un coût de "362 176" a été obtenue. Puisque la limite inférieure affichée dans le message 1 était «338864», nous pouvons voir qu'il existe une solution optimale (solution exacte) dans au moins la plage de «[338864, 362176]». Plus la différence (écart) entre le coût de la solution provisoire et la limite inférieure est petite, meilleures sont les performances de CBC.

Messages 4 ~ 6

Message 4

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

Le résultat du prétraitement appelé ** DiveCoefficient [^ 5], [^ 6] ** s'affiche. (Je ne connais pas les détails.) En conséquence, la solution provisoire a encore été mise à jour pour faire de l'écart une section de «[338864, 340160]».

Message 5

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

Il semble que l'algorithme de coupe est en cours d'exécution. En particulier, afin d'améliorer les bornes supérieure et inférieure du ** problème double **, il semble qu'il essaie des coupes qui suppriment les valeurs décimales de la solution d'atténuation obtenue. Dans cet exemple, il semble que 5 types de coupes aient été effectuées. Les détails sont affichés au bas du journal.

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

Les 0e, 1re et 3e coupes semblent être suffisantes pour ce problème. (Vous pouvez voir que Gomory Cut [^ 7] et Clique Cut sont particulièrement efficaces.) Il a été déterminé que la limite supérieure du problème dual est «340160». Le coût de la solution provisoire est également «340160», vous pouvez donc voir que c'est la solution optimale.

Message 6

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

La valeur finale du coût et le temps de calcul sont affichés. Pour ce problème, le nœud racine a une solution réalisable suffisamment bonne et la limite supérieure du problème double, de sorte qu'aucun élagage supplémentaire du procédé de coupe de branche n'est effectué.

Messages 7, 8

Ces messages sont les journaux que vous voyez lorsque vous calculez le problème le plus difficile (air04). Dans air04, cette recherche semble être effectuée avant la méthode de limitation de branche. Le nombre de nœuds recherchés par la recherche d'arborescence de la méthode de limitation moléculaire et le nombre de nœuds qui n'ont pas encore été recherchés sont affichés. Chaque fois qu'un nouvel entier est obtenu, des informations sur son coût et la méthode utilisée sont affichées. (Message 8)

Voici comment lire le journal. Pour référence, le journal lors du calcul de «air03» et «air04» à l'aide de python-mip est téléchargé ci-dessous. https://github.com/Noriaki416/Qiita/tree/master/CBC_log

air0 # _cbc_log.txt sera le journal.

réglage

En lisant les journaux, vous pouvez voir quel processus est le goulot d'étranglement dans la résolution du problème. Vous devriez être en mesure d'améliorer les performances de la solution en identifiant la cause et en optimisant. Les paramètres de réglage détaillés sont décrits après p6 du pdf au début.

Lors du réglage avec Pulp, il semble que vous puissiez le spécifier avec options. Il est expliqué en détail dans le blog ci-dessous.

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

options vous permet de définir d'autres options CBC. Par exemple, pour utiliser l'option maxsol, définissez options = ['maxsol 1']. L'option maxsol vous permet de spécifier le nombre de solutions provisoires trouvées avant la fin du calcul. Si vous voulez une solution réalisable, même si ce n'est pas la solution optimale, vous pouvez utiliser maxsol 1 pour la trouver plus rapidement. Je peux le faire.

Les paramètres autres que «maxsol» sont également décrits sur le site GAMS [^ 8]. Il peut être intéressant de voir la différence en jouant avec différentes choses.

C'est ça. Si vous avez des suggestions, n'hésitez pas à nous contacter.