scip - 了解 SCIP 中的显示输出和分支切割机制
问题描述
我试图理解使用 SCIP 使用分支和剪切代码解决 MILP 时显示输出的含义。我使用 TSP 示例作为参考。
time | node | left |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr| dualbound | primalbound | gap | compl.
p 1.9s| 1 | 0 | 0 | - | vbounds| 0 |1861 | 130 | 126 | 0 | 0 | 3 | 0 | 0.000000e+00 | 5.523000e+03 | Inf | unknown
2.2s| 1 | 0 | 1320 | - | 15M | 0 |1861 | 130 | 126 | 0 | 0 | 3 | 0 | 9.795000e+02 | 5.523000e+03 | 463.86%| unknown
2.2s| 1 | 0 | 1321 | - | 15M | 0 |1861 | 130 | 126 | 0 | 0 | 3 | 0 | 9.800000e+02 | 5.523000e+03 | 463.57%| unknown
4.6s| 1 | 0 | 1341 | - | 15M | 0 |1861 | 130 | 128 | 2 | 1 | 3 | 0 | 9.800000e+02 | 5.523000e+03 | 463.57%| unknown
4.6s| 1 | 0 | 1393 | - | 15M | 0 |1861 | 130 | 129 | 3 | 2 | 3 | 0 | 9.800000e+02 | 5.523000e+03 | 463.57%| unknown
4.7s| 1 | 0 | 1422 | - | 15M | 0 |1861 | 130 | 136 | 10 | 3 | 3 | 0 | 9.800000e+02 | 5.523000e+03 | 463.57%| unknown
4.8s| 1 | 0 | 1472 | - | 16M | 0 |1861 | 130 | 139 | 13 | 4 | 3 | 0 | 9.860000e+02 | 5.523000e+03 | 460.14%| unknown
4.8s| 1 | 0 | 1472 | - | 16M | 0 |1861 | 130 | 139 | 13 | 4 | 3 | 0 | 9.860000e+02 | 5.523000e+03 | 460.14%| unknown
4.9s| 1 | 0 | 1479 | - | 17M | 0 |1861 | 130 | 144 | 18 | 5 | 3 | 0 | 9.925000e+02 | 5.523000e+03 | 456.47%| unknown
4.9s| 1 | 0 | 1480 | - | 17M | 0 |1861 | 130 | 144 | 18 | 5 | 3 | 0 | 9.930000e+02 | 5.523000e+03 | 456.19%| unknown
5.0s| 1 | 0 | 1489 | - | 17M | 0 |1861 | 130 | 148 | 22 | 6 | 3 | 0 | 9.930000e+02 | 5.523000e+03 | 456.19%| unknown
5.0s| 1 | 0 | 1530 | - | 17M | 0 |1861 | 130 | 151 | 25 | 7 | 3 | 0 | 9.930000e+02 | 5.523000e+03 | 456.19%| unknown
5.1s| 1 | 0 | 1558 | - | 17M | 0 |1861 | 130 | 153 | 27 | 8 | 3 | 0 | 9.957500e+02 | 5.523000e+03 | 454.66%| unknown
5.1s| 1 | 0 | 1559 | - | 17M | 0 |1861 | 130 | 153 | 27 | 8 | 3 | 0 | 9.960000e+02 | 5.523000e+03 | 454.52%| unknown
5.2s| 1 | 0 | 1680 | - | 17M | 0 |1861 | 130 | 160 | 34 | 9 | 3 | 0 | 1.019750e+03 | 5.523000e+03 | 441.60%| unknown
time | node | left |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr| dualbound | primalbound | gap | compl.
5.2s| 1 | 0 | 1681 | - | 17M | 0 |1861 | 130 | 160 | 34 | 9 | 3 | 0 | 1.020000e+03 | 5.523000e+03 | 441.47%| unknown
5.4s| 1 | 0 | 1795 | - | 17M | 0 |1861 | 130 | 165 | 39 | 10 | 3 | 0 | 1.040500e+03 | 5.523000e+03 | 430.80%| unknown
5.4s| 1 | 0 | 1796 | - | 17M | 0 |1861 | 130 | 165 | 39 | 10 | 3 | 0 | 1.041000e+03 | 5.523000e+03 | 430.55%| unknown
5.5s| 1 | 0 | 1822 | - | 17M | 0 |1861 | 130 | 170 | 44 | 11 | 3 | 0 | 1.041000e+03 | 5.523000e+03 | 430.55%| unknown
5.6s| 1 | 0 | 1859 | - | 18M | 0 |1861 | 130 | 162 | 48 | 12 | 3 | 0 | 1.041000e+03 | 5.523000e+03 | 430.55%| unknown
5.7s| 1 | 0 | 1880 | - | 18M | 0 |1861 | 130 | 172 | 58 | 13 | 3 | 0 | 1.041000e+03 | 5.523000e+03 | 430.55%| unknown
5.8s| 1 | 0 | 1917 | - | 18M | 0 |1861 | 130 | 177 | 63 | 14 | 3 | 0 | 1.044500e+03 | 5.523000e+03 | 428.77%| unknown
5.8s| 1 | 0 | 1918 | - | 18M | 0 |1861 | 130 | 177 | 63 | 14 | 3 | 0 | 1.045000e+03 | 5.523000e+03 | 428.52%| unknown
5.9s| 1 | 0 | 1993 | - | 18M | 0 |1861 | 130 | 182 | 68 | 15 | 3 | 0 | 1.047643e+03 | 5.523000e+03 | 427.18%| unknown
5.9s| 1 | 0 | 1994 | - | 18M | 0 |1861 | 130 | 182 | 68 | 15 | 3 | 0 | 1.048000e+03 | 5.523000e+03 | 427.00%| unknown
6.0s| 1 | 0 | 2022 | - | 18M | 0 |1861 | 130 | 171 | 70 | 16 | 3 | 0 | 1.048750e+03 | 5.523000e+03 | 426.63%| unknown
6.0s| 1 | 0 | 2023 | - | 18M | 0 |1861 | 130 | 171 | 70 | 16 | 3 | 0 | 1.049000e+03 | 5.523000e+03 | 426.50%| unknown
6.1s| 1 | 0 | 2106 | - | 18M | 0 |1861 | 130 | 176 | 75 | 17 | 3 | 0 | 1.052250e+03 | 5.523000e+03 | 424.88%| unknown
6.1s| 1 | 0 | 2107 | - | 18M | 0 |1861 | 130 | 176 | 75 | 17 | 3 | 0 | 1.053000e+03 | 5.523000e+03 | 424.50%| unknown
6.3s| 1 | 0 | 2148 | - | 19M | 0 |1861 | 130 | 178 | 77 | 18 | 3 | 0 | 1.053375e+03 | 5.523000e+03 | 424.31%| unknown
time | node | left |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr| dualbound | primalbound | gap | compl.
6.3s| 1 | 0 | 2149 | - | 19M | 0 |1861 | 130 | 178 | 77 | 18 | 3 | 0 | 1.054000e+03 | 5.523000e+03 | 424.00%| unknown
6.4s| 1 | 0 | 2210 | - | 20M | 0 |1861 | 130 | 162 | 81 | 19 | 3 | 0 | 1.054167e+03 | 5.523000e+03 | 423.92%| unknown
6.5s| 1 | 0 | 2211 | - | 20M | 0 |1861 | 130 | 162 | 81 | 19 | 3 | 0 | 1.055000e+03 | 5.523000e+03 | 423.51%| unknown
6.6s| 1 | 0 | 2269 | - | 20M | 0 |1861 | 130 | 165 | 84 | 20 | 3 | 0 | 1.058111e+03 | 5.523000e+03 | 421.97%| unknown
6.6s| 1 | 0 | 2270 | - | 20M | 0 |1861 | 130 | 165 | 84 | 20 | 3 | 0 | 1.059000e+03 | 5.523000e+03 | 421.53%| unknown
6.7s| 1 | 0 | 2276 | - | 20M | 0 |1861 | 130 | 166 | 85 | 21 | 3 | 0 | 1.059000e+03 | 5.523000e+03 | 421.53%| unknown
8.3s| 1 | 2 | 2700 | - | 21M | 0 |1861 | 136 | 166 | 85 | 23 | 9 | 22 | 1.066655e+03 | 5.523000e+03 | 417.79%| unknown
*14.4s| 30 | 25 | 4452 | 75.0 | LP | 7 |1861 | 136 | 138 | 125 | 0 | 9 | 167 | 1.067000e+03 | 5.459000e+03 | 411.62%| 0.86%
29.9s| 100 | 91 | 6915 | 46.9 | 23M | 17 |1861 | 147 | 145 | 288 | 2 | 20 | 654 | 1.067000e+03 | 5.459000e+03 | 411.62%| 1.46%
*33.4s| 131 | 100 | 7858 | 42.9 |strongbr| 18 |1861 | 153 | 144 | 349 | 1 | 26 | 788 | 1.067000e+03 | 1.530000e+03 | 43.39%| 1.53%
42.5s| 200 | 155 | 9970 | 38.7 | 24M | 18 |1861 | 170 | 142 | 455 | 2 | 43 |1097 | 1.067000e+03 | 1.530000e+03 | 43.39%| 2.17%
51.6s| 300 | 237 | 13159 | 36.4 | 26M | 18 |1861 | 224 | 139 | 640 | 2 | 97 |1277 | 1.067000e+03 | 1.530000e+03 | 43.39%| 2.33%
57.4s| 400 | 309 | 15846 | 34.0 | 27M | 19 |1861 | 238 | 152 | 820 | 2 | 113 |1426 | 1.067000e+03 | 1.530000e+03 | 43.39%| 3.10%
63.4s| 500 | 391 | 19168 | 33.9 | 29M | 24 |1861 | 319 | 145 | 926 | 2 | 195 |1560 | 1.067000e+03 | 1.530000e+03 | 43.39%| 3.22%
L68.4s| 584 | 111 | 22609 | 34.9 | rins| 26 |1861 | 330 | 149 |1016 | 1 | 256 |1619 | 1.067000e+03 | 1.127000e+03 | 5.62%| 10.59%
我还曾经display display对显示输出中的列标题的含义有所了解。
cons只是问题中的全局有效约束
rows是当前节点中的 LP 行数
cuts是应用于 LP 的削减总数
sepa是在当前节点执行的分离轮数
所以我对此有几个问题。我假设问题开始时行应该为 0，但我不确定为什么问题开始时有 126 行。我使用以下函数添加 LP 行：
SCIP_ROW *row;
SCIP_CALL(SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, "subtour_elimination", -SCIPinfinity(scip), tour.size(), FALSE, FALSE, TRUE));
是cuts由 SCIP 自动添加的吗？
SCIP 如何将全局有效的约束添加到约束池？它取自rows或取自cuts或取自两者？有没有办法直接从约束处理程序添加全局有效的约束？
解决方案
TSP 示例是 SCIP 团队用来突出 SCIP 约束能力的最流行示例之一。您可以在SCIP 简介的幻灯片中找到此示例的数学模型，即节约束整数编程。
LP 松弛最初由所谓的节点度约束组成，它要求每个节点与解决方案中的两条边恰好相邻。subtour 消除约束在 LP 中作为没有行的单个约束存在，但仅在必要时将实际线性行添加到 LP 松弛中。
其他通用分隔符（例如 Gomory 或 CMIR 分割）在整个搜索过程中都处于活动状态。您可以使用display statistics和浏览“分离器”部分以了解启用了哪些切割平面方法。
为了检查初始 LP 松弛，您可以使用 SCIP 必须将当前模型转储到 LP 文件中的各种写入可能性。
例如，您可以在初始根 LP 松弛后停止 SCIP（只需及时按 CTRL + C）并使用
write lp tsp.lp对于 LP 松弛write mip tsp.lp用于 MIP 松弛write transproblem tsp.cip对于当前转换的问题
前两种方法仅限于 LP 格式，可读性很好。只有最后一种格式，即 SCIP 自己的 CIP 格式，也会打印 subtour-elimination 约束。添加到当前 LP 松弛的行/切割可能不是转换问题的一部分。
tldr; 明智地选择打印放松的格式:)
推荐阅读
- c++ - 为什么 for 循环中的异步不能提高执行时间？
- python - 对于多维（numpy）数组，Python 中的 a[x] 和 a[x, :] 有什么区别？
- javascript - 反应 JS 问题以映射对象名称
- java - 如何使用 github java API (org.eclipse.egit.github.*) 通过邮件搜索用户
- powershell - 使用 XAML 将输出重定向到 PowerShell 中的文本框
- javascript - 如何构建从 HTML / JavaScript 表单传递的消息？
- python - 如何绘制从 scipy.brute() 方法输出的 4-D 数据？
- reactjs - 状态内部动态创建的组件在商店更改时不会更新
- apache-kafka - 无法消费 Kafka 消息
- r - 在 R 中处理复杂的列表