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. > ______________________________________________ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.