## 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:

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:

and for Gurobi:

Solved in 40291 iterations and 141.13 seconds

1. Dual simplex as I assume GuRoBi use is usually quite fast. The specialized network flow optimizer in MOSEK (or in CPLEX) may be even faster.

Erling

2. If a GAMS program with your problem is available somewhere then let me know.

Erling

3. No doubt a better engineered network code will improve this by a large margin (e.g. Cplex network algorithm solves these models in 0.25 and 1.58 seconds). Then we are comparing network codes. However, the point I wanted to make, somewhat inarticulate no doubt, was that a standard lp solver does not always have to be slow compared to specialized solvers. Anyway, the problems are in GAMS, and can be retrieved from http://amsterdamoptimization.com/models/assignmentR.zip.

4. Erwin makes a good point. Sparse LP solvers are so fast that they are competitive with the performance of many special-purpose solvers. Furthermore, many problems with special structure - such as network models - have side constraints. And once you consider side constraints, you're usually better off with a general purpose solver.

5. I totally agree with both dual simplex is surprisingly fast. That was also the intended implication of my initial post.

It is amazing it can compete with a specialized network simplex solver.

6. Just a quick note. We downloaded your GAMS model. Thanks. MOSEK has a mode where it detect the embedded network structure.
But GAMS or at least the GAMS/MOSEK link puts the objective in the constraints because in GAMS you do

min z

st c'x = z
...

so we should change MOSEK so it take that into account.

7. Sorry, my last put should say if the objective is in the constraints then the problem does not have network structure and hence we will detect the embedded network structure.