Tuesday, November 17, 2009

Assignment Problem

In http://thread.gmane.org/gmane.comp.lang.r.general/169477/focus=169690 an assignment problem is formed and solved with the Hungarian method in R:

assign

Current LP solvers are very fast: when we solve this with Gurobi we see:

Presolve time: 0.34 sec.
Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0    0.0000000e+00   1.000000e+03   0.000000e+00      0s
    8329    7.4610203e+02   3.115000e+03   0.000000e+00      5s
   11696    7.5580772e+02   0.000000e+00   0.000000e+00      9s

Solved in 11696 iterations and 9.30 seconds

I.e. about three times as fast. So not just any specialized algorithm can beat an excellent general purpose LP solver at all times.

Note: for n=1000 the timings for R are:

assign2and for Gurobi:

Solved in 40291 iterations and 141.13 seconds