Предлагая нижнюю оценку для решателя ILP

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

Легко вычислить тривиальную нижнюю границу для объективного значения моей проблемы минимизации, но в выводе CPLEX (столбец Best Bound) я вижу, что он даже близко не подходит в течение долгого и долгого времени. Он находит действительно хорошие решения почти сразу, но ошибочно полагает, что оптимальное решение может быть намного лучше.

Теперь я должен признать, что на самом деле не знаю, как работают эти решатели, но похоже, что они тратят время, пытаясь улучшить смехотворно слабые нижние границы, охотясь за невероятно оптимистичными решениями. Итак, мои вопросы:

  1. Может ли указание решателю приличной нижней границы цели помочь ему быстрее пройти?

  2. Если да, то какие решатели могут принять известную нижнюю границу, предоставленную в качестве дополнительного ввода?

В качестве иллюстрации я вставляю первые несколько строк вывода CPLEX из примера выполнения (который продолжается гораздо дольше, без дальнейшего улучшения цели и мучительно медленного улучшения наилучшей границы):

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap
      0     0     -388.6997   178                   -388.6997        9
*     0+    0                          297.0000     -388.6997        9  230.88%
*     0+    0                          275.0000     -388.6997        9  241.35%
      0     2     -388.6997   178      275.0000     -387.8106        9  241.02%
*    20+   20                          185.0000     -307.6363       80  266.29%
*    30+   30                          135.0000     -307.6363       90  327.88%
*    30+   30                           94.0000     -307.6363       90  427.27%
*    60+   60                           90.0000     -307.6363      120  441.82%
*   160+  126                           77.0000     -307.6363      272  499.53%
*   200+   93                           12.0000     -307.4836      325     ---
    300   182     -135.2988   107       12.0000     -268.6638      466     ---
   1200   934      -50.6022    85       12.0000     -206.2938     1480     ---
   2197  1755      -96.9612    93       12.0000     -189.8013     2470     ---
   3226  2600       -2.8316    87       12.0000     -179.9669     3480     ---
   4374  3521     -156.2442   110       12.0000     -170.4183     4567     ---
   5490  4421     -128.0871    97       12.0000     -167.3696     5623     ---
   6971  5603     -147.5022   108       12.0000     -162.4180     7055     ---
   8739  6997     -103.5374   113       12.0000     -156.3532     8673     ---

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

Источник

1 ответ

Если у вас есть хорошая нижняя граница из возможного решения, вы можете предоставить это как начало MIP для CPLEX.

Затем CPLEX попытается улучшить это решение и проигнорировать все ветви в своем алгоритме ветвления и границ, у которых граница ниже этой.

Более подробную информацию вы можете найти здесь: https://www.ibm.com/support/knowledgecenter/SS9UKU_12.5.0/com.ibm.cplex.zos.help/UsrMan/topics/discr_optim/mip/para/49_mipStarts.html

Источник
Другие вопросы по тегам