Эффективный и быстрый способ решения задач линейного программирования в R

Question

Я работаю с очень большим набором данных, обычно имея дело с несколькими миллионами комбинаций. Я хочу, чтобы решить эту проблему присваивания. (Максимизации суммы) я пытался решить ее на небольшой тестовый набор с использованием adagio::assignment, clue::solve_LSAP

Я не был в состоянии успешно установить «lpSolve» пакет на моей системе, подбросил ошибку сегментации

Хотел бы узнать, какой из них быстрее или любой другой способ, который делает это быстрее.

Спасибо ....

Answer 1

ЛП формулировка является не хороший способ решить проблему назначения, в зависимости от того библиотеки вы используете. Вы должны использовать венгерский алгоритм, и он выглядит так: solve_LSAP делает именно это.

Не нужно ничего пробовать ИМХО.

EDIT: Эффективная реализация венгерского метода должна быть O (n^3), что чрезвычайно быстро для любого алгоритма оптимизации. Если solve_LSAP недостаточно быстро для вашей проблемы (предполагается, что она выполнена правильно), маловероятно, что какой-либо точный метод будет работать. Вам нужно будет использовать какую-то эвристику для приближения решения.