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

10 comments:

  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

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

    Erling

    ReplyDelete
  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.

    ReplyDelete
  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.

    ReplyDelete
  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.

    ReplyDelete
  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.

    ReplyDelete
  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.

    So your examplepoint out a problem in the GAMS/MOSEK link.

    ReplyDelete
  8. GAMS has an objective variable instead of an objective function. If the objvar appears only once (linearly) in the model, and has no bounds, it can be substituted out. Most links do that automatically so the solver sees a proper objective function. This is especially important for nonlinear solvers.

    ReplyDelete
  9. These reformulations are explained in the documentation for the GAMS IO library. You may want to ask GAMS for a copy.

    ReplyDelete
  10. I think GAMS has new link structure. As far as I understand our link should be rewritten soon and that will solve this problem.

    Btw the specialized network flow alg in MOSEK does much better than dual simplex on your assignment problem. We will most likely provide Mittleman with a few cases. They will be good for his network solver test.

    ReplyDelete