Блог

Я часто использую Gurobi с JuMP и заметил, что в его выводах все еще есть части, которые я не понимаю. Если это где-то не задокументировано и ссылка была бы наиболее желанной, не могли бы вы помочь понять следующее? 🙂

 Found heuristic solution: objective 5820.0000000
Presolve removed 33 rows and 11 columns
Presolve time: 0.00s
Presolved: 607 rows, 331 columns, 2445 nonzeros
Variable types: 111 continuous, 220 integer (220 binary)

Root relaxation: objective 1.157500e 03, 64 iterations, 0.00 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0 1157.50000    0   25 5820.00000 1157.50000  80.1%     -    0s
H    0     0                    2535.0000000 1157.50000  54.3%     -    0s
     0     0 1236.00000    0   23 2535.00000 1236.00000  51.2%     -    0s
     0     0 1273.65351    0   41 2535.00000 1273.65351  49.8%     -    0s
     0     0 1274.59375    0   41 2535.00000 1274.59375  49.7%     -    0s
     0     0 1274.69841    0   42 2535.00000 1274.69841  49.7%     -    0s
     0     0 1309.98305    0   42 2535.00000 1309.98305  48.3%     -    0s
     0     0 1310.26027    0   42 2535.00000 1310.26027  48.3%     -    0s
     0     0 1340.01176    0   47 2535.00000 1340.01176  47.1%     -    0s
     0     0 1342.47826    0   49 2535.00000 1342.47826  47.0%     -    0s
     0     0 1342.60000    0   49 2535.00000 1342.60000  47.0%     -    0s
     0     0 1362.32468    0   50 2535.00000 1362.32468  46.3%     -    0s
     0     0 1363.08000    0   49 2535.00000 1363.08000  46.2%     -    0s
     0     0 1363.13077    0   49 2535.00000 1363.13077  46.2%     -    0s
     0     0 1370.79545    0   53 2535.00000 1370.79545  45.9%     -    0s
     0     0 1375.50000    0   52 2535.00000 1375.50000  45.7%     -    0s
     0     0 1375.50000    0   52 2535.00000 1375.50000  45.7%     -    0s
     0     0 1376.70025    0   52 2535.00000 1376.70025  45.7%     -    0s
     0     0 1376.70122    0   53 2535.00000 1376.70122  45.7%     -    0s
     0     0 1376.70122    0   53 2535.00000 1376.70122  45.7%     -    0s
     0     2 1376.98418    0   53 2535.00000 1376.98418  45.7%     -    0s
*  255   157              14    2457.0000000 1473.00000  40.0%  22.5    0s
H  407   223                    2397.0000000 1548.00000  35.4%  20.3    0s
* 1962   758              22    2355.0000000 1772.85714  24.7%  16.8    0s
*14326  2205              27    2343.0000000 2088.50000  10.9%  15.7    3s
 

Из того, что, как мне кажется, я уже знаю, в порядке появления:

Предварительное решение

• Найдено эвристическое решение: задача 5820, Gurobi запустил предварительное решение и нашел решение со значением 5820
• Предварительное решение удалило 33 избыточных или бесполезных переменных, а также 11 ограничений?
• Предварительно заданные: размеры модели предварительно определены
• Типы переменных: некоторые являются двоичными, а некоторые непрерывными.
• Корневая релаксация: релаксация LP имеет цель 1 157,5

Узлы

• Expl (1): * пустой или H, я не знаю разницы, когда есть эти символы, но я заметил, что все строки с заданным символом (H, * или пустой) будут иметь одинаковые выходные данные.
• Увеличьте и уменьшите количество исследованных узлов и неисследованных узлов в дереве решений.

Текущий Узел

• Объект: цель текущего исследуемого узла?
• Глубина: глубина дерева, на которой в данный момент находится решение
• ИнтИнф: Я понятия не имею об этом

Объективные Границы

• Действующий сотрудник: текущее значение найденного наилучшего допустимого решения
• BestBd: Лучшая нижняя граница, найденная в настоящее время
• Разрыв: Это, вероятно, разрыв между текущим лучшим решением и наилучшей оценкой, но я не мог понять, как он вычисляется.

Работа

• It/Узел: Здесь нам нужно найти, что такое итерация
• Время: Время, потраченное на решение до тех пор.

Подробную информацию можно найти по адресу https://www.gurobi.com/documentation/9.1/refman/mip_logging.html.

Позвольте мне просто привести те, которые отвечают на ваш вопрос:

Nodes Раздел (первые две колонки) содержит общую количественную информацию о ходе поиска. В первом столбце показано количество узлов ветвления и разреза, которые были исследованы до этого момента, а во втором-количество конечных узлов в дереве поиска, которые остаются неисследованными. Иногда в начале выходной строки будет символ H или*. Это указывает на то, что было найдено новое возможное решение либо с помощью эвристики MIP (H), либо с помощью ветвления (*).

В Current Node этом разделе представлена информация о конкретном узле, который был исследован в этой точке дерева ветвей и срезов. Он показывает цель связанной релаксации, глубину этого узла в дереве ветвей и разрезов и количество целых переменных, которые имеют нецелые значения в связанной релаксации.

В Objective Bounds разделе представлена информация о наиболее известном целевом значении для возможного решения (т. е. о целевом значении текущего сотрудника) и текущей целевой привязке, предоставляемой конечными узлами дерева поиска. Оптимальное объективное значение всегда находится между этими двумя значениями. Третий столбец в этом разделе ( Gap ) показывает относительный разрыв между двумя объективными границами. Когда этот разрыв меньше, чем MIPGap параметр, оптимизация завершается.

Work Раздел журнала содержит информацию о том, сколько работы было выполнено к этому моменту. В первом столбце показано среднее число симплексных итераций, выполняемых на узел в дереве ветвей и разрезов. В последнем столбце показано время, прошедшее с начала решения.

Глядя на свой журнал, вы очень быстро приближаетесь к оптимальности, и вы получаете решение Gap=0,01%, вероятно, за полминуты или около того.