help-glpk
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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


From: Leow, Woei Ling
Subject: Re: [Help-glpk] How to tell if lpx_simplex() needs to be restarted?
Date: Wed, 12 Apr 2006 22:16:36 +0800

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




reply via email to

[Prev in Thread] Current Thread [Next in Thread]