Что произойдет, если я изменил правую часть ограничения (GLPK)?

Я увеличиваю правую часть ограничения "меньше или равно" для проблемы MIP с помощью GLPK. Однако иногда после повторной оптимизации GLPK не может найти какое-либо возможное решение в отведенные сроки. Поэтому я предполагаю, что он не проверяет, было ли возможно предыдущее решение. У кого-нибудь есть опыт в этом? Или можно указать мне документ, который не является исходным кодом?

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

Ваше здоровье!


glpk gurobi coin-or-cbc cplex scip
person pbc1303    schedule 13.06.2018    source источник
comment
Некоторые решатели MIP имеют функцию MIPSTART. ГЛПК нет.   -  person Erwin Kalvelagen    schedule 14.06.2018

Ответы (2)


arrow_upward
3
arrow_downward

После изменения чего-либо в модели вся информация о решении обычно отбрасывается, и проблема решается с нуля. Даже если вы смягчили проблему, это не обязательно означает, что ее легче решить для решателя MIP, в частности, это всегда может приводить к другим решениям LP, которые вызывают разное ветвление, первичный эвристический запуск из другой начальной точки и не повезло в конце концов. Так что, в конце концов, вам может просто не повезти, потому что решающая программа теперь занимает больше времени.

Выполнить «теплый старт» в решающей программе MIP довольно сложно. SCIP предоставляет такую ​​функциональность, см. http://scip.zib.de/doc-5.0.1/html/REOPT.php, но это работает только в том случае, если вы измените объективные коэффициенты или ужесточите ограничения (это основано на предположении, что все, что было невозможно раньше, по-прежнему невозможно, поэтому вам нужно только поиск снова только в допустимой части дерева).

Однако в вашем конкретном случае уже поможет просто сохранить возможные решения и попробовать их в следующем прогоне. Это то, что SCIP делает по умолчанию. Кроме того, SCIP (как и все упомянутые вами альтернативы) должен быть намного более стабильным и производительным, чем GLPK. См. http://plato.asu.edu/ftp/milpc.html для эталонный тест решателей MIP на MIPLIB 2010, стандартный набор тестов MIP: GLPK может решить 2 из 87 экземпляров в течение 2 часов, в то время как CBC решает 53, SCIP решает 76, а CPLEX и Gurobi решают все 87 экземпляров . Также Xpress и SAS очень хорошо показали себя в наборе тестов.

person Gerald    schedule 13.06.2018
comment
Спасибо за ответ! Я понимаю, что другие решатели могут быть более надежными, но у меня есть некоторые технологические ограничения для демонстрации, и для этого мне придется придерживаться GLPK. Ваше здоровье! - person pbc1303; 13.06.2018

arrow_upward
0
arrow_downward

Ясно, что если вы ослабите формулировку, проблема не может стать невыполнимой (если это было возможно раньше). Значит, либо вы что-то неправильно интерпретируете, либо в коде есть ошибка.

Я так понимаю, вы еще не пробовали другой решатель. Вы обязательно должны это сделать. В общем, все те, которые вы упомянули в своем вопросе, считаются более надежными / стабильными, чем GLPK.

person mattmilten    schedule 13.06.2018
comment
Я предполагаю, что вы что-то неверно истолковываете, потому что OP говорил о том, что больше не находит решение в срок. :-) - person Gerald; 13.06.2018
comment
Верно, должно быть, меня подсунули! - person mattmilten; 13.06.2018