Скорость решения линейного программирования ojAlgo

Question

Я довольно новичок в линейном программировании, я решил свою первую проблему с lpsolve (двоичная dll, вызываемая из Java, через обертку JavaILP, чтобы иметь более объектно-ориентированный код), и это было очень быстро (50 мс).

Затем я решил избежать нативного кода (если это возможно) и переписал все, используя ojAlgo, и для моей проблемы с 2100 переменными время решения увеличилось с 50 мс до 1089 мс.

Эта скорость нормальная / ожидаемая?

Это потому, что ojAlgo использует BigDecimal (не уверен, что это так, я видел doubles в коде там и там) и lpsolve, вероятно, использует ints?

Могу ли я что-нибудь с этим сделать?

С другой стороны, найденный максимум увеличился с 1013 в OPTIMAL 1249, и это хорошо. (используя lpsolve я даже не знал, что существует лучшее решение)

редактировать: я не заметил, что несколько имен выражений конфликтовали, и я думаю, что это заставило их перезаписывать друг друга; Теперь я исправил это и OPTIMAL 1013 решение найдено… за 8270 мс.

Answer 1

Совершенно нормально для чистого Java-решателя быть медленнее, чем нативный код.

У вас есть целочисленные переменные? Если вы это сделаете, то это MIP, и это может быть довольно сложно решить.

ojAlgo разделяет модель и решатель. Модель использует BigDecimal для внутреннего использования. Модель анализирует проблему и вызывает различные решатели в зависимости от характеристик проблемы. Решатели могут работать с любым числовым типом, который они хотят. Встроенные решатели ojAlgo работают с примитивным дублем.

Вы можете подключить любой решатель, который вам нравится в ojAlgo. Уже есть интеграции для 3 лучших коммерческих решателей:

https://github.com/optimatika/ojAlgo-extensions/tree/develop/ojAlgo-cplex

https://github.com/optimatika/ojAlgo-extensions/tree/develop/ojAlgo-gurobi

https://github.com/optimatika/ojAlgo-extensions/tree/develop/ojAlgo-mosek

Есть также другие чистые Java, с открытым исходным кодом, LP решатели:

https://github.com/optimatika/ojAlgo-extensions/tree/develop/ojAlgo-joptimizer

https://github.com/optimatika/ojAlgo-extensions/tree/develop/ojAlgo-commons-math3

Там еще нет интеграции для lpsolve...