CODEWITHSUNDEEP
roptimizationlinear-programming
abcdef
abcdef

Reputation: 41

Efficient and fast way of solving linear programming problems in R

I am working with a very large dataset, typically dealing with a few millions of combinations. I want to solve the assignment problem.(maximise the sum) I had tried solving it on a small test set using adagio::assignment, clue::solve_LSAP

I wasnt able to successfully install the "lpSolve" package on my system, threw some segmentation fault

Wanted to know which of these is faster or any other method which does it faster.

Thanks....

Upvotes: 1

Views: 1163

Answers (1)

Nicolas Grebille
Nicolas Grebille

Reputation: 1332

An LP formulation is not a good way to solve the assignment problem, whichever library you use. You have to use the Hungarian algorithm, and it looks like solve_LSAP does exactly that.

No need to try anything else IMHO.

EDIT: An efficient implementation of the Hungarian method should be O(n^3), which is extremely fast for any optimization algorithm. If solve_LSAP is not fast enough for your problem (assumed it is implemented correctly), it is very unlikely that any exact method will work. You will have to use some sort of heuristic to approximate the solution.

Upvotes: 2

Related Questions