Monday, February 28, 2011

Network extraction

Not sure what is going on here, but it seems that GAMS/Mosek only is able to extract a network on smaller problems. Basically I suggested a type of transportation model for a client problem. I received some data for a small problem, and to check how the model performs I just multiply the number of nodes in the network by a number K. For K<14 I see something like:

Simplex network detection is started.
Number of network constraints: 585
Number of network variables  : 57798
Simplex network detection is terminated.

But for K≥14, when things become more interesting, I see:

Simplex network detection is started.
Number of network constraints: 0
Number of network variables  : 0
Simplex network detection is terminated.

Just to make sure I am not crazy, I also checked with Cplex. That gave for K=14:

Extracted network with 631 nodes and 67662 arcs, including slacks.
Extraction time =    0.02 sec.

I suspect there is something wrong with the GAMS/Mosek link. Apart from this Mosek is actually doing very well on this problem.

Note: GAMS is quite fast in generating this model. It still beats the solvers. Mosek/primal did very will on the largest instance I tried (K=100 with 4600 rows, 4.8M variables and 13M nonzeroes) with a solution time of 50 seconds. GAMS generated this model in 38 seconds.

10 comments:

  1. I would try switching off presolve and scaling.

    ReplyDelete
  2. That does not help. I suspect the link does not properly substitute out the objective variable (a GAMS quirk) before passing the model to Mosek.

    ReplyDelete
  3. Have you tried to run on a exported mps file ? You will have to contact mosek support for a better reply, since I do not work for mosek. Are these models pure network or with side constraints ?

    ReplyDelete
  4. MOSEK support here.

    The GAMS quirk you talk about might very well be the issue. Michael Bussieck is working on a new MOSEK interface. I think that might solve it. At least it would be interesting to check if the new interface also has the issue.

    You are of course also welcome to contact MOSEK support. If we can get the problem we might be able to do something about it.

    ReplyDelete
  5. I have learned from Michael Bussieck that you have newest version, so it is not the obj. issue.

    I think there is a bug in the code but without seeing example data it is close to impossible to fix.

    ReplyDelete
  6. I have uploaded files demonstrating this here:
    K13.gms and K14.gms. Good luck!

    ReplyDelete
  7. Thanks again for the upload.

    I now have a fix so if you input a pure network then MOSEK should always discover it. You can see the result below. I will notify Michael at GAMS about it. You can talk to him about a new version.


    Simplex network detection is started.
    Number of network constraints: 630
    Number of network variables : 67032
    Simplex network detection is terminated.
    Simplex network optimizer started.
    Primal simplex network optimizer started.
    Primal simplex network optimizer setup started.
    Primal simplex network optimizer setup terminated.
    Optimizer - solved problem : the primal
    Optimizer - constraints : 630 variables : 67032
    Optimizer - hotstart : no
    ITER DEGITER(%) PFEAS DFEAS POBJ DOBJ TIME TOTTIME
    0 0.00 0.00e+00 NA -0.0000000000e+00 NA 0.02 0.11
    2096 0.00 0.00e+00 NA 2.6746955210e+02 NA 0.03 0.12
    Primal simplex network optimizer terminated.
    Simplex network optimizer terminated.
    2096 0.00 0.00e+00 NA 2.6746955210e+02 NA 0.04 0.12
    Primal simplex optimizer terminated.
    Simplex optimizer terminated. Time: 0.14.
    Optimizer terminated. Time: 0.16

    Solution summary
    Basic solution
    Problem status : PRIMAL_AND_DUAL_FEASIBLE
    Solution status : OPTIMAL
    Primal - objective: 2.6746955210e+02 eq. inf.: 0.00e+00 max bound inf.: 0.00e+00
    Dual - objective: 2.6746955210e+02 eq. inf.: 0.00e+00 max bound inf.: 0.00e+00

    ReplyDelete