[R] LSAP and the Hungarian algorithm [was: R-help]

[Hans W Borchers]

Ravi Varadhan <rvaradhan <at> jhmi.edu> writes:
> 
> However, The "clue" package has the solve_LSAP() function (as pointed out by
> Hans Werner)  that solves the linear sum assignment problem, but it uses the
> Hungarian algorithm that was requested by you.
> 
> The lp.assign() function in "lpSolve" package (as pointed out by Girish)
> also solves the linear sum assignment problem, but I do not know which
> algorithm is used.  This is not documented in the help page.  

lp.assign() solves the linear assignment problem as a standard linear program
with binary variables, see the "Assignment Problem" article in the Wikipedia.
With 'lpSolve', this will be slower than the Hungarian algorithm in higher
dimensions.

But remember our thread "A combinatorial optimization problem: finding the
best permutation of a complex vector" in Nov. 2009. Highly efficient software
for integer programming -- such as ILOG's commercial CPLEX program -- will be
much faster than the specialized Hungarian algorithm when the problem size
grows considerably (as was shown in Erwin Kalvelagen's blog).

Hans Werner

> Best,
> Ravi.
>