Monday, December 7, 2015

1000 x 1000 assignment problem: 10 hours?

In http://stackoverflow.com/questions/34096450/how-to-increase-the-efficiency-when-you-have-1000x1000-matrix-in-excel a user reports that for a 1000x1000 assignment problem, OpenSolver takes more than 10 hours. I guessed that an LP/MIP solver should not take more than a few minutes. Let me check with a GAMS model:

image

The first thing we notice is that GAMS takes 25 seconds to generate this model. We can improve on this a little bit by adding option limrow=0 (and to be complete limcol=0) to reduce the size of the listing file. Probably we also should turn off the solution listing (option solprint=off) to reduce time on the way back. This gives us a generation time of 19 seconds, and a solution time of 5 seconds with the open source solver CBC. The total turnaround time is 32 seconds. About a speedup of 100k.  For these super easy models we see that solving time may be less than generation time.

Interestingly Cplex takes more time than CBC: 25 seconds vs 5 seconds (both using default settings). This is because Cplex tries very hard to presolve the model (20 seconds). This is actually not a bad thing: I prefer Cplex to work hard there so the more difficult models solve faster. Loosing a bit on simple problems is not a big deal.