Почему GLPSOL (GLPK) занимает много времени, чтобы решить большой MIP?

Question

У меня проблема с большим MIP, и я использую GLPSOL в GLPK для ее решения. Однако решение проблемы релаксации ЛП занимает много итераций, и каждая итерация значений obj и infeas одинакова. Я думаю, что он нашел оптимальное решение, но он не остановится и продолжает работать в течение многих часов. Это произойдет для каждой крупномасштабной проблемы MIP/LP? Как я могу справиться с такими случаями? Может ли кто-нибудь дать мне какие-либо предложения по этому поводу? Благодаря!

Answer 1

Проблема решения MIP полностью NP-полная, что означает, что есть случаи, которые не могут быть эффективно решены. Но часто наши проблемы имеют достаточно структуру, поэтому эвристика может помочь решить эти модели. Это позволило добиться огромных успехов в решении задач за последние десятилетия (overview).

Для понимания базового подхода и понимания того, что конкретно представляет собой проблема в вашем случае (нет прогресса в верхнем пределе, никакого прогресса в нижней границе, ...), читайте Practical Guidelines for Solving Difficult Mixed Integer Linear Programs.

Имейте в виду, что существуют большие промежутки между коммерческими решателями, такими как Gurobi/Cplex и некоммерческими в целом (особенно в MIP-решении). Существует огромное количество тестов here.

Есть также множество параметров для настройки. Например, у Gurobi есть разные шаблоны параметров: один нацелен на быстрые результаты возможного решения; один предназначен для доказательства границ.

Мое личное мнение: по сравнению с cbc (с открытым исходным кодом) & scip (с открытым исходным кодом, но не бесплатно для коммерческого использования), GLPK очень плохо.