Понимание вывода на дисплей в SCIP и механизме ветвления и разрезания - PullRequest
Новая
       35

Понимание вывода на дисплей в SCIP и механизме ветвления и разрезания

0 голосов
/ 05 августа 2020

Я пытаюсь понять значение вывода на дисплей при использовании SCIP для решения MILP с использованием кода Branch-and-Cut. Я использую пример 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 или с обоих? Есть ли способ добавить глобально допустимые ограничения непосредственно из обработчика ограничений?

1 Ответ

1 голос
/ 05 августа 2020

Пример TSP - один из самых популярных примеров, которые команда SCIP использует, чтобы выделить возможности ограничения SCIP. Вы можете найти математическую модель этого примера на слайдах этого введения в SCIP , Целочисленное программирование с ограничениями раздела.

Релаксация LP изначально состоит из так называемых узловых ограничений, которые требуют, чтобы каждый узел примыкал ровно к двум ребрам в решении. Ограничение исключения субтура присутствует в качестве единственного ограничения без строки в LP, но только добавляет фактические линейные строки к релаксации LP, если необходимо. поиск. Вы можете использовать display statistics и просмотреть раздел «Разделители», чтобы узнать, какие методы секущей плоскости были включены.

Чтобы проверить начальную релаксацию LP, вы можете использовать различные возможности записи, которые SCIP имеет для сброса текущую модель в LP-файл.

Вы можете, например, остановить SCIP после начальной root LP-релаксации (просто нажмите CTRL + C своевременно) и используйте

  • write lp tsp.lp для релаксации LP
  • write mip tsp.lp для релаксации MIP
  • write transproblem tsp.cip для текущей преобразованной задачи

Первые два метода ограничены формат LP, который хорошо читается. Только последний формат, собственный формат CIP SCIP, также будет печатать ограничения исключения субтура. Строки / сокращения, которые были добавлены к текущей релаксации LP, могут не быть частью преобразованной задачи.

tldr; выбирайте с умом, в каком формате распечатать релаксацию :)

...