[Top][All Lists]
[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: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] How to tell if lpx_simplex() needs to be restarted? |
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
- Re: [Help-glpk] How to tell if lpx_simplex() needs to be restarted?, (continued)
- Re: [Help-glpk] How to tell if lpx_simplex() needs to be restarted?, Andrew Makhorin, 2006/04/10
- Re: [Help-glpk] How to tell if lpx_simplex() needs to be restarted?, leowl, 2006/04/11
- Re: [Help-glpk] How to tell if lpx_simplex() needs to be restarted?, leowl, 2006/04/11
- Re: [Help-glpk] How to tell if lpx_simplex() needs to be restarted?, leowl, 2006/04/11
- Re: [Help-glpk] How to tell if lpx_simplex() needs to be restarted?, leowl, 2006/04/11
- Re: [Help-glpk] How to tell if lpx_simplex() needs to be restarted?, leowl, 2006/04/11
- Re: [Help-glpk] How to tell if lpx_simplex() needs to be restarted?, leowl, 2006/04/11
- Re: [Help-glpk] How to tell if lpx_simplex() needs to be restarted?, leowl, 2006/04/11
- Re: [Help-glpk] How to tell if lpx_simplex() needs to be restarted?, leowl, 2006/04/11
- Re: [Help-glpk] How to tell if lpx_simplex() needs to be restarted?,
Andrew Makhorin <=
- Re: [Help-glpk] How to tell if lpx_simplex() needs to be restarted?, Leow, Woei Ling, 2006/04/12
- RE: [Help-glpk] How to tell if lpx_simplex() needs to be restarted?, Meketon, Marc, 2006/04/13