Почему эту смешанную целочисленную программу так неэффективно решать?

Я пытаюсь решить MIP, используя GLPK и CBC, и ни один из решателей не может эффективно найти решение. Журнал решателя GLPK показывает, что он быстро находит решение, которое находится в пределах 0,1% от истинного оптимума, но затем поиск этого истинного оптимума занимает целую вечность.

Я знаю, что могу использовать miptol arg для установки допуска - мой вопрос в том, что в этой проблеме делает решатель настолько неэффективным при поиске истинного оптимума? Я обычно решаю версии этой задачи с немного другими входными данными, и они решаются менее чем за секунду.

Вот файл с моей спецификацией проблемы, который можно запустить в ГЛПК с glpsol --cpxlp anonymizedlp.lp.

А ниже приведена часть журнала GLPK — вы увидите, что почти оптимальное решение MIP найдено за 54 000 итераций, а затем дерево ветвей начинает расти и расти:

GLPSOL: GLPK LP/MIP Solver, v4.61
Parameter(s) specified in the command line:
 --cpxlp /var/folders/g6/fs71g8j575v4_whqythqw7h40000gn/T/11446-pulp.lp -o
 /var/folders/g6/fs71g8j575v4_whqythqw7h40000gn/T/11446-pulp.sol
Reading problem data from '/var/folders/g6/fs71g8j575v4_whqythqw7h40000gn/T/11446-pulp.lp'...
664 rows, 781 columns, 2576 non-zeros
443 integer variables, 338 of which are binary
3195 lines were read
GLPK Integer Optimizer, v4.61
664 rows, 781 columns, 2576 non-zeros
443 integer variables, 338 of which are binary
Preprocessing...
213 constraint coefficient(s) were reduced
524 rows, 652 columns, 2246 non-zeros
318 integer variables, 213 of which are binary
Scaling...
 A: min|aij| =  1.282e-01  max|aij| =  1.060e+07  ratio =  8.267e+07
GM: min|aij| =  7.573e-01  max|aij| =  1.320e+00  ratio =  1.744e+00
EQ: min|aij| =  6.108e-01  max|aij| =  1.000e+00  ratio =  1.637e+00
2N: min|aij| =  3.881e-01  max|aij| =  1.355e+00  ratio =  3.491e+00
Constructing initial basis...
Size of triangular part is 524
Solving LP relaxation...
GLPK Simplex Optimizer, v4.61
524 rows, 652 columns, 2246 non-zeros
      0: obj =  -0.000000000e+00 inf =   2.507e+02 (195)
    238: obj =  -5.821025664e+06 inf =   0.000e+00 (0)
*   363: obj =  -7.015287886e+04 inf =   0.000e+00 (0) 1
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
+   363: mip =     not found yet <=              +inf        (1; 0)
+  8606: mip =     not found yet <=  -7.015289436e+04        (8239; 0)
+ 13027: mip =     not found yet <=  -7.015289436e+04        (12660; 0)
+ 16367: mip =     not found yet <=  -7.015289436e+04        (16000; 0)
+ 19135: mip =     not found yet <=  -7.015289436e+04        (18768; 0)
+ 21523: mip =     not found yet <=  -7.015289436e+04        (21156; 0)
+ 23667: mip =     not found yet <=  -7.015289436e+04        (23300; 0)
+ 25415: mip =     not found yet <=  -7.015289436e+04        (25048; 0)
+ 27260: mip =     not found yet <=  -7.015289436e+04        (26893; 0)
+ 29055: mip =     not found yet <=  -7.015289436e+04        (28688; 0)
+ 30770: mip =     not found yet <=  -7.015289436e+04        (30403; 0)
+ 32362: mip =     not found yet <=  -7.015289436e+04        (31995; 0)
Time used: 60.0 secs.  Memory used: 14.1 Mb.
+ 33876: mip =     not found yet <=  -7.015289436e+04        (33509; 0)
+ 35338: mip =     not found yet <=  -7.015289436e+04        (34971; 0)
+ 36721: mip =     not found yet <=  -7.015289436e+04        (36354; 0)
+ 38080: mip =     not found yet <=  -7.015289436e+04        (37713; 0)
+ 39372: mip =     not found yet <=  -7.015289436e+04        (39005; 0)
+ 40601: mip =     not found yet <=  -7.015289436e+04        (40234; 0)
+ 41837: mip =     not found yet <=  -7.015289436e+04        (41470; 0)
+ 43036: mip =     not found yet <=  -7.015289436e+04        (42669; 0)
+ 44192: mip =     not found yet <=  -7.015289436e+04        (43825; 0)
+ 45350: mip =     not found yet <=  -7.015289436e+04        (44983; 0)
+ 46374: mip =     not found yet <=  -7.015289436e+04        (46007; 0)
+ 47281: mip =     not found yet <=  -7.015289436e+04        (46914; 0)
Time used: 120.0 secs.  Memory used: 20.4 Mb.
+ 48220: mip =     not found yet <=  -7.015289436e+04        (47853; 0)
+ 49195: mip =     not found yet <=  -7.015289436e+04        (48828; 0)
+ 50131: mip =     not found yet <=  -7.015289436e+04        (49764; 0)
+ 51110: mip =     not found yet <=  -7.015289436e+04        (50743; 0)
+ 52131: mip =     not found yet <=  -7.015289436e+04        (51764; 0)
+ 53092: mip =     not found yet <=  -7.015289436e+04        (52725; 0)
+ 53901: >>>>>  -7.015398607e+04 <=  -7.015289436e+04 < 0.1% (53532; 0)
+ 61014: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (57365; 3302)
+ 64785: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (61136; 3302)
+ 67671: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (64022; 3302)
+ 70330: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (66681; 3302)
+ 72613: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (68964; 3302)
+ 74731: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (71082; 3302)
Time used: 180.0 secs.  Memory used: 29.9 Mb.
+ 76685: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (73036; 3302)
+ 78508: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (74859; 3302)
+ 80220: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (76571; 3302)
+ 81852: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (78203; 3302)
+ 83368: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (79719; 3302)
+ 84815: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (81166; 3302)
+ 86126: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (82477; 3302)
+ 87358: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (83709; 3302)
+ 88612: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (84963; 3302)
+ 89821: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (86172; 3302)
+ 90989: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (87340; 3302)
+ 92031: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (88382; 3302)

glpk coin-or-cbc linear-programming integer-programming
person thomaskeefe    schedule 26.05.2017    source источник

Ответы (2)


arrow_upward
3
arrow_downward

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

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

Хотя это не отвечает на ваш вопрос о том, почему эта проблема сложна для GLPK или CBC, она, по крайней мере, несложна для SCIP, который также имеет открытый исходный код и бесплатен для ученых. Скорее всего одна из эвристик не реализована в других решателях, т.к. отключение эвристик в SCIP значительно усложняет поиск решения - ветвление просто не решает эту проблему.

Вам нужна правильная эвристика.

person mattmilten    schedule 29.05.2017

arrow_upward
3
arrow_downward

Теория

Даже 0-1 целочисленное программирование является NP-hard, что в основном означает, что не существует эффективного алгоритма (для общей проблемы), если только P=NP.

Что это означает для вашей проблемы:

Это означает, что есть задачи, которые могут быть смоделированы как MIP, содержат всего 100 переменных и меньше и ваш решатель не может их решить (оптимально). Позвольте мне быть более ясным: для каждого MIP-решателя, который вы мне даете, я могу построить экземпляр, может быть, со 100 переменными, которые ваш решатель не может решить (это можно сделать для каждой проблемы, которая является NP-сложной, хотя мы говорим об общих целочисленное программирование здесь).

Подход к NP-сложным проблемам заключается в использовании предположений о вашей проблеме и ваших данных, чтобы иметь возможность сократить экспоненциально большое пространство поиска (которое необходимо пройти для каждой NP-сложной проблемы). Но: P!=NP означает, что не существует алгоритма, который мог бы сделать это (используя специфические для проблемы вещи) для всех проблем в целом (частично связанных: Теорема о бесплатном обеде не существует)! Следствие: все хорошие MIP-решатели созданы для решения общих проблем, которые важны для многих людей и где из-за этого были разработаны хорошие и полезные эвристики (например, секущие плоскости).

Итак, теперь мы знаем, что все успешные MIP-решатели являются эвристическими, настроенными на более быстрое решение более распространенных проблем и могут эффектно потерпеть неудачу в других задачах (опять же: теорема об отсутствии бесплатного обеда). Это не исчезнет, ​​учитывая приведенные выше предположения. Может помочь использование разных решателей и настройка разных параметров (утрированно: разные параметры = разные решатели)!

Есть еще по крайней мере одна вещь, которую нужно сказать:

Даже если мы ограничимся, скажем, простой задачей упаковки в контейнеры, есть простые и сложные экземпляры. Некоторые из них будут решены мгновенно, а другие никогда не остановятся. Очень сложно проанализировать, какие экземпляры сложные, а какие нет. Но эти различия влияют на, возможно, очень высокую дисперсию в отношении времени решения, что является естественным следствием NP-сложности!

Существует несколько интересных (основанных на статистической физике) исследований о проблеме SAT, где исследователи обнаружили и количественно оценили феномен фазового перехода, который говорит нам, какие проблемы (с точки зрения соотношения переменных и предложений) сложны в отношении случайных формул.

(Некоторые вводные записи в блоге, посвященные этому: Решатели SAT: сложно или просто?

Практика (только замечания)

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

Что касается параметров, следует отметить, что параметры в целом могут быть настроены на:

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

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

Также можно проверить полные и неполные методы (пример в мире SAT: DPLL/CDCL и стохастический поиск), чтобы решить проблемы оптимизации и понять, почему некоторые настройки лучше добиваются определенного прогресса = получить лучшую цель, в то время как другие лучше доказывают, что мы достигли минимума.

person sascha    schedule 26.05.2017