Предложение нижней границы для решателя 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 (потому что я могу доказать это более простым методом) и особенно не с отрицательным целевым значением (потому что это невозможно даже в моей модели).


pyomo mathematical-optimization coin-or-cbc integer-programming cplex
person bela_a_holdon    schedule 14.10.2016    source источник
comment
(1) Вы всегда можете добавить ограничение, которое делает все решения ниже вашей априори известной границы недопустимыми. Этого было бы достаточно (2) Что касается коммерческих решателей, я читал не один раз, что разработчики считают, что это часто контрпродуктивно. Но, возможно, это поможет в вашем случае (и, к сожалению, я не могу предоставить ссылку; возможно, Google ответит на вопрос в списке рассылки gurobi). (3) В зависимости от того, чего вы достигли, вы можете настроить параметры решателя. У Гуроби есть опция MIPFocus. Может быть, вы тоже сможете этого добиться. Например, много сокращений для лучшего доказательства границ; больше эвристики для более быстрых хороших решений   -  person sascha    schedule 15.10.2016
comment
Как вы пришли к тривиальной оценке снизу? Вы просто ослабили ограничения целостности и решили (настоящую) линейную программу?   -  person Rodrigo de Azevedo    schedule 15.10.2016
comment
@sascha Добавление ограничения к цели не помогло, но я посмотрю на Gurobi и (3), спасибо. Возможно, это именно то, что мне нужно.   -  person bela_a_holdon    schedule 15.10.2016
comment
Также прочтите это.   -  person sascha    schedule 15.10.2016
comment
@RodrigodeAzevedo Нет, это просто некоторые операции с данными, более простая комбинаторная задача, чем та, которую я хочу решить. Но неотрицательность моей цели уже была бы достаточно хорошей: прогрессирование нижней границы требует времени, чтобы достичь тривиального нуля, после чего это не займет слишком много времени.   -  person bela_a_holdon    schedule 15.10.2016

Ответы (1)


arrow_upward
1
arrow_downward

Если у вас есть хорошая нижняя граница из возможного решения, вы можете предоставить это как начало 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

person Realhermit    schedule 17.02.2017