Вопрос или проблема
Я пишу код на C++, и оказалось, что мне нужно решить задачу оптимизации, которая может быть сформулирована с использованием m переменных и n линейных ограничений (т.е. ограничение i имеет вид \sum_j a_{i,j} x_j >= b_i; хотя, если вы не знаете, что такое линейное программирование, то, вероятно, не сможете ответить на этот вопрос).
Так получилось, что количество переменных довольно маленькое — скажем, обычно меньше 10; но количество ограничений значительно больше.
Мне нужно, чтобы решение было быстрым — как минимум в среднем (надеюсь, не более одного прохода по большинству ограничений) — и я готов пожертвовать расстоянием от оптимума ради этого.
Существует ли библиотека для этого “нишевого” линейного программирования? Если нет, какие существуют быстрые библиотеки для линейного программирования в общем?
Требования:
- Свободная лицензия
- Исходный код доступен
- Работает на Linux
- Работает на x86_64
- Быстрая
- Бесплатная
Желаемые характеристики:
- Действительно быстрая
- Способность менять точность на скорость
- Мультиплатформенная
- C++ вместо C
- Современный C++ вместо C++98/03
- Хорошо документированная
Я изучаю CLP от COIN-OR. Это C++ FOSS решатель задач линейного программирования; на данный момент не могу сказать о нем много.
Здесь есть два аспекта для обсуждения:
- Алгоритм.
- Реализация (1) на подходящем языке.
Алгоритм — это то, что определяет время выполнения и точность метода. Если вы готовы пожертвовать точностью, вы могли бы выбрать метод, такой как IP вместо симплексного метода (это пример для иллюстрации).
Что касается реализации — учитывая, что задачи этого рода обычно решаются с помощью матричных операций, вы можете использовать классическую библиотеку для таких вещей — BLAS. Другой вариант — это пакет GLPK. Если вам нужна демонстрация того, как использовать последний, взгляните на исходный код пакета Octave. Возможно, документация по теме от Octave может быть полезной.
Кстати, другой способ сделать компромисс, независимо от конкретной техники, заключается в выполнении вычислений в формате меньшей точности, например float32, а не float64.
Ответ или решение
Поиск быстрого и приближенного решателя для задачи линейного программирования с малым числом переменных и множеством ограничений требует учесть ряд факторов, как в выборе алгоритма, так и его реализации. Рассмотрим более подробно:
Алгоритм
-
Внутренняя точка vs Симплекс: Методы внутренней точки (Interior Point Methods) могут быть предпочтительны, если вы готовы немного пожертвовать точностью ради увеличения скорости решения. В противоположность этому, классический симплекс-метод часто предоставляет точные решения, но может быть менее эффективен при большом количестве ограничений.
-
На основе ограниченного уравнения: При большом количестве ограничений и малом количестве переменных (менее 10) также может быть целесообразным рассмотреть специализированные алгоритмы, которые создают оптимизацию из ограниченного множества переменных, выбирая наиболее влияющие ограничения.
Реализация
-
CLP от COIN-OR: Это один из популярных открытых решателей линейного программирования, который подходит под описанные требования, включая поддержку либеральной лицензии и возможность использования на платформе Linux x86_64. Однако стоит обратить внимание на то, насколько активно поддерживается данный проект и соответствуют ли последняя версия удовлетворяющим требованиям к производительности.
-
BLAS и GLPK: BLAS предоставляет базовые подпрограммы линейной алгебры, которые могут быть полезны для оптимизации вычислений. GLPK (GNU Linear Programming Kit) — это другой популярный выбор с открытым исходным кодом. GLPK поддерживает как симплекс-метод, так и метод внутренней точки, и хорошо документирован, что упрощает его интеграцию в C++ проекты.
-
Использование BLASFEO: Для высокоэффективных вычислений BLASFEO может предложить интерфейсы, которые специфически оптимизированы под микроархитектуру процессоров x86_64.
Рекомендации
-
Современный C++: Важно убедиться, что выбранная библиотека предлагает API на современном C++ (C++11 и новее), что облегчит интеграцию и уменьшит количество потенциальных ошибок.
-
Автоматическое уменьшение точности: Предусмотрите возможность использования арифметики с пониженной разрядностью, где это возможно, например, вместо
float64используйтеfloat32. Это может существенно ускорить вычисления за счет уменьшения объема обрабатываемых данных.
Заключение
Итак, при проектировании решения для задачи линейного программирования с небольшим числом переменных, но множеством ограничений, важно выбрать эффективный алгоритм и реализовать его, используя правильные библиотеки и инструменты. Используйте исследования и тестирование, чтобы подобрать оптимальный баланс скорости и точности, соответствующий вашим бизнес-требованиям.