Разъяснение терминов, используемых в командах SCIP «проблема с отображением» и «запись статистики» - PullRequest
Новая
       50

Разъяснение терминов, используемых в командах SCIP «проблема с отображением» и «запись статистики»

1 голос
/ 12 марта 2020

Я прочитал в некоторых .cnf файлах, используя SCIP, и меня смущают используемые термины. Я также не могу найти эти термины в любой документации SCIP.

1) Когда после чтения в файл .cnf набирается «проблема с отображением», я вижу следующее: 

Problem name:

Variables:

Constraints: x initial, y maximal

Что означают initial и maximal в этом контексте?

2) Когда набирается optimize, SCIP выводит строку каждые 100 итераций по умолчанию. Существует столбец с именем confs, который обозначает конфликты. Что означает конфликт в этом случае?

Относится ли это к оговоркам о конфликте? Или же это относится к конфликту одного и того же типа в обучении на основе конфликта (CDCL), где оно относится к одной и той же переменной, принимающей 2 разных значения одновременно в графе конфликтов, и, таким образом, является конфликтом?

3 ) После ввода write statistics появляется раздел дерева B & B, подобный следующему: 

B&B Tree           :

  number of runs   :         11

  nodes            :      46620 (32430 internal, 14190 leaves)

  feasible leaves  :          0

  infeas. leaves   :      14189

  objective leaves :          0

  nodes (total)    :     264828 (185078 internal, 79750 leaves)

  nodes left       :         36

  max depth        :        187

  max depth (total):        970

  backtracks       :      14238 (30.5%)

  early backtracks :          0 (0.0%)

  nodes exc. ref.  :          0 (0.0%)

  delayed cutoffs  :      18206

  repropagations   :      43176 (2316736 domain reductions, 13733 cutoffs)

  avg switch length:       2.71

  switching time   :     100.16

В чем разница между узлами и узлами (всего)?

В настоящее время я понимаю узлы как число узлов SCIP удалось прочесать до настоящего времени с текущим временем, в то время как узлы (всего) относится к общему количеству узлов, которое имеет вся проблема.

4) Что означает число прогонов? Из приведенной выше статистики c означает ли это, что ветвь и граница запускаются с нуля 11 раз?

5) В чем разница между максимальной глубиной и максимальной глубиной (всего)?

I в настоящее время понимают максимальную глубину как максимальную глубину дерева B & B, достигнутого до сих пор, в то время как максимальная глубина (общая) - это максимальная глубина дерева B & B, которую может достичь вся проблема.

6) Что означает репропагация?

В данный момент я не понимаю этого.

7) Что означает отсрочка отсрочки?

Я не понимаю этого на момент.

8) Что такое длина и время переключения?

В данный момент я не понимаю этого.

1 Ответ

0 голосов
/ 12 марта 2020

Это много вопросов. Я постараюсь ответить на все, что я могу:

1) исходное число ограничений при чтении проблемы. Обработчики ограничений могут добавлять дополнительные ограничения, поэтому максимальное количество ограничений может быть больше.

2) SCIP не является чисто решателем SAT, поэтому я думаю, что ответ не тот. Для статьи о том, как анализ конфликтов работает в MIP-решателях, я бы посоветовал взглянуть на: https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6406

3) общее количество узлов - это количество узлов за все прогоны (10 перезапусков в вашем случае ), это узлы только с текущего прогона

4) да, вы перезапускаете 10 раз, поэтому 11 прогонов. Я предполагаю, что вы установили акцент на cpsolver, поскольку SCIP обычно перезапускается только один раз.

5) нет, он такой же, как и с количеством узлов. maxdepth total - это максимальная глубина, достигнутая за все перезапуски

6) репропагации - это когда вновь решенный узел распространяется снова, например, для изучения дополнительных конфликтов

7) отсроченное отсечение, насколько это возможно. я знаю, когда узел (который был создан ранее, но не решен) находится в поддереве, которое было обрезано.

8) при выборе нового узла фокуса у вас есть путь переключения из текущий к новому узлу фокуса. Средняя длина коммутатора - это средняя длина этого пути (и то же самое для времени)

...