RE: [Help-glpk] How to tell if lpx_simplex() needs to be restarted?

[Meketon, Marc]

Instead of network simplex, check out Andrew Goldberg's network solver
that uses a scaling minimum-cost algorithm:
http://www.avglab.com/andrew/soft.html

It doesn't have the range of options, modeling language, and so on as
glpk, but it's free for academic use (or at least it use to be) and in
my experience runs very fast on large problems.  I only have experience
with a version of it that's about 7 years old.

-----Original Message-----
From: address@hidden
[mailto:address@hidden On Behalf
Of Leow, Woei Ling
Sent: Wednesday, April 12, 2006 10:17
To: address@hidden
Cc: address@hidden
Subject: Re: [Help-glpk] How to tell if lpx_simplex() needs to be
restarted?

Hi Andrew,

Thanks for taking a look at the problem data. You are spot on- these are
network simulations. 

Does your conclusion apply to the bigger problem data set as well? Or is
it applicable only to the smaller set? I notice that the smaller
problems get solved occassionally while it is much harder to get one of
the larger ones solved.

Also, was it possible to solve the larger problem data set?

In the meantime, I will look into network simplex. Is network simplex on
the roadmap of glpk?

Thank you so much!

Regards,
Woei Ling


---------- Original Message ----------------------------------
From: Andrew Makhorin <address@hidden>
Reply-To: Andrew Makhorin <address@hidden>
Date:  Wed, 12 Apr 2006 16:34:29 +0400

>Hi Woei Ling
>
>> Please find attached the
>> problem data set. Please let me know if you think having another
>> set of data will help you in diagnosing the problem.
>
>Thank you. Your instances are classic example which beats the glpk
>simplex at all :+) I solved your small problem without any troubles,
>however the convergence was extremely slow due to high degeneracy:
>all constraints are equalities most of which have zero rhs (looking
>through the constraint matrix I guess it is a pure network problem).
>
>lpx_read_mps: reading problem data from `small.mps'...
>lpx_read_mps: problem network_
>lpx_read_mps: 9249 rows, 18084 columns, 206628 non-zeros
>lpx_read_mps: 128822 cards were read
>lpx_simplex: original LP has 9249 rows, 18084 columns, 206628 non-zeros
>lpx_simplex: presolved LP has 9248 rows, 9316 columns, 197312 non-zeros
>lpx_adv_basis: size of triangular part = 9088
>      0:   objval =   0.000000000e+00   infeas =   1.000000000e+00
(128)
>    126:   objval =   2.088068648e+01   infeas =   4.353815783e-18
(112)
>*   126:   objval =   2.088068648e+01   infeas =   2.220446049e-16
(112)
>*   200:   objval =   1.446037689e+01   infeas =   3.885780586e-16 (99)
>*   400:   objval =   8.348297709e+00   infeas =   0.000000000e+00 (70)
>*   600:   objval =   8.348297709e+00   infeas =   0.000000000e+00 (26)
>*   800:   objval =   8.348297709e+00   infeas =   0.000000000e+00 (22)
>*  1000:   objval =   8.348297709e+00   infeas =   0.000000000e+00 (21)
>. . . . . . .
>* 50200:   objval =   7.462112984e+00   infeas =   8.411967574e-13 (16)
>* 50361:   objval =   7.462112984e+00   infeas =   0.000000000e+00 (16)
>OPTIMAL SOLUTION FOUND
>Time used:   896.0 secs
>Memory used: 30.1M (31515772 bytes)
>
>In principle, glpk simplex is able to solve your problem; however,
>I would suggest to use more specialized methods like network simplex
>(it is not implemented in glpk) or a version of out-of-kilter
>algorithm, because they would obtain the solution much faster.
>
>Andrew Makhorin
>
>
____________________________________________________________

Sent via the AlumMail https://alumni.nus.edu.sg


_______________________________________________
Help-glpk mailing list
address@hidden
http://lists.gnu.org/mailman/listinfo/help-glpk
---------------------------------------------------------------------------- 
This e-mail and any attachments may be confidential or legally privileged.  If 
you received this message in error or are not the intended recipient, you 
should destroy the e-mail message and any attachments or copies, and you are 
prohibited from retaining, distributing, disclosing or using any information 
contained herein.  Please inform us of the erroneous delivery by return e-mail. 

Thank you for your cooperation.
----------------------------------------------------------------------------