Существует ли программное обеспечение Integer Linear Programming, которое возвращает также неоптимальные решения?

Question

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

Итак, LP-Solver, который, например, останавливается через некоторое время и возвращаетлучшее решение, которое он нашел до сих пор, сделало бы работу.

Есть ли такое программное обеспечение?Было бы замечательно, если бы это программное обеспечение было открытым или, по крайней мере, бесплатным, как в пиве.

В качестве альтернативы: есть ли другой способ, который обычно ускоряет проблемы с Integer LP?Это правильное место, чтобы спросить?

Answer 1

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

Как вы, возможно, знаете, целочисленное программирование - это NP-сложная задача, и существует реальное искусство быстрого поиска оптимальных решений и хороших выполнимых решений. Для сравнения различных решателей см. тесты для оптимизации программного обеспечения проф. Ханса Миттельмана . Контрольные показатели MILP, в частности MIPLIB2010 и ТЭО, должны быть наиболее актуальными.

В дополнение к выбору хорошего решателя, есть много вещей, которые можно сделать для улучшения времени решения, включая настройку параметров решателя и переформулировку модели. Многие люди в области исследований и промышленности, в том числе и я, проводят свою карьеру, работая над улучшением времени решения моделей MIP, как в целом, так и для конкретных моделей.

Если вы являетесь академическим пользователем, обратите внимание, что лучшие коммерческие системы, такие как CPLEX и Gurobi, бесплатны для академического использования. См. Соответствующие веб-сайты для деталей.

Наконец, вы можете захотеть взглянуть на OR-Exchange , дочерний сайт Stack Overflow, который фокусируется на области исследования операций.

(Отказ от ответственности: в настоящее время я работаю в Gurobi Optimization и ранее работал в ILOG, которая предоставила CPLEX).

Answer 2

Если вы хотите быстро получить целочисленное решение feasibel и если вам не нужно оптимальное решение, вы можете попробовать

1. Увеличение относительного или абсолютного разрыва . Обычно решатели имеют небольшие разрывы, например, 0,0001% для относительного разрыва. Это означает, что решатель будет продолжать поиск решений MIP до тех пор, пока решение MIP не окажется на расстоянии менее 0,0001% от оптимального решения. Увеличьте это значение, например. 1%., Так что вы получите хорошее решение, но решатель не потратит много времени на доказательство оптимальности.

2. Попробуйте различные значения параметров решателя, касающиеся Эвристика MIP .

3. CPLEX и GUROBI имеют параметры для управления, MIP-акцент . Это означает, что решатель будет уделять больше внимания поиску возможных решений или доказательству оптимальности. Уделять особое внимание возможным решениям MIP.

Большинство решателей, таких как CPLEX, Gurobi, MOPS или GLPK, имеют настройки для разрыва и эвристики. MIP акцент может быть установлен - насколько я знаю - только в CPLEX и Gurobi.

Answer 3

Насколько я знаю, CPLEX может.Он может возвращать пул решений, который содержит первичные выполнимые решения в поиске, и если вы указываете фокус поиска на выполнимости, а не на оптимальности, можно генерировать более выполнимые решения.В конце вы можете просто экспортировать пул.Вы можете использовать пул, чтобы сделать горячий старт, так что это зависит от вас.CPlex сейчас бесплатен, по крайней мере, в моей стране, так как вы можете зарегистрироваться в качестве исследователя.

Answer 4

Обычный подход к решению ILP - это ветвление и ограничение. Это использовало решение многих sub-LP (без-I). Окончательно оптимальный результат - лучший из всех суб-LP. Поскольку найдено хотя бы одно решение, вы можете остановиться в любое время, и пока у вас будет лучшее.

Один пакет, который может это сделать, это бесплатный lpsolve. Посмотрите там на set_timeout для определения ограничения по времени, и когда это ILP, функция решения может вернуть в SUPOPTIMAL значение best_so_far.

Answer 5

Не могли бы вы принять во внимание Microsoft Solver Foundation?Единственное ограничение - это технологический стек, который вы предпочитаете, и здесь вы должны использовать, как вам кажется, технологии Microsoft: C #, vb.net и т. Д. Вот пример того, как использовать его с Excel: http://channel9.msdn.com/posts/Modeling-with-Solver-Foundation-30

Что касается вашего вопроса, возможно, у вас не будут полностью оптимизированные решения, если вы установите эффективность (например, 85% или 0,85).В результате вы можете увидеть все возможные решения для такого ограничения.