RE: [Help-glpk] Do I misunderstand LPX_K_ITMLM?

[Robert Horvath]

The problem you have supplied does not seem to be a MIP problem (no Generals
section).
Would you look into it again?

Actually I am suspecting a bug here that I ran into before, and patched glpk
for it. The problem is, that in case of numerical instability (that means
too big round off errors I think) the simplex solver tries to pivot on
elements that are supposed to be zero, but are not exatly zero because of
round off errors. This way the system runs (or can run)into an infinite
loop. If I could reproduce your error, I could see if my patch corrects it
or not. 

Regards
Robert

> -----Original Message-----
> From: Philip Warner [mailto:address@hidden
> Sent: Wednesday, April 14, 2004 3:46 PM
> To: Robert Horvath
> Cc: address@hidden
> Subject: RE: [Help-glpk] Do I misunderstand LPX_K_ITMLM?
> 
> At 08:16 PM 14/04/2004, Robert Horvath wrote:
> >Could you supply an lp form of the problem?
> 
> Hit it again; this time a little more information - just before it seems
> to go into an infinite loop, it reports:
> 
>      spx_simplex: numerical instability (dual simplex)
> 
> then pauses for a long time, and finally starts outputting lots of simplex
> status messages. A section of output is below:
> 
>      *    12:   objval =  6.986620375e+002   infeas =  3.166666860e-012
> (0)
>      *    13:   objval =  6.982902211e+002   infeas =  3.166666114e-012
> (0)
>      OPTIMAL SOLUTION FOUND
>       200
>      lpx_write_mps: writing problem data to
> `E:\VB_Work\Inca2\INCAApp\MixTest\LR-Int\last_problem_int.mps'...
>      LP = 217000088, ITLIM: 10000
>      Integer optimization begins...
>      +    13: mip =     not found yet; lp =  6.982902211e+002 (1, 0)
>      +   141: mip =  4.435402310e+007; lp =  6.982902211e+002 (105, 110)
>      +   646: mip =  2.204301650e+007; lp =  6.982902211e+002 (337, 498)
>      +   653: mip =  2.130181650e+007; lp =  6.982902211e+002 (246, 597)
>      +   690: mip =  2.037800700e+007; lp =  6.982902211e+002 (236, 629)
>      +   790: mip =  8.772860500e+006; lp =  6.982902211e+002 (222, 793)
>      +   893: mip =  8.406606500e+006; lp =  6.986174367e+002 (258, 929)
>      +  1033: mip =  8.383514000e+006; lp =  6.986174367e+002 (204, 1133)
>      spx_simplex: numerical instability (dual simplex)
>      spx_simplex: numerical instability (dual simplex)
>      * 59600:   objval =  6.461142600e+006   infeas =  5.752142934e-017
> (1)
>      * 59800:   objval =  6.461142600e+006   infeas =  5.752142934e-017
> (1)
>      * 60000:   objval =  6.461142600e+006   infeas =  5.752142934e-017
> (1)
>      ...etc...
>      * 72600:   objval =  6.461142600e+006   infeas =  5.752142934e-017
> (1)
>      * 72800:   objval =  6.461142600e+006   infeas =  5.752142934e-017
> (1)
>      * 73000:   objval =  6.461142600e+006   infeas =  5.752142934e-017
> (1)
> 
> ...this is in a call to lpx_integer, with a limit of 2000 iterations.
> 
> The attached zip file contains the LPT and MPS versions of the problem.
> Please let me know if there is anything else I need to provide.
> 
> Thanks again for your help,
> 
> Philip Warner
> 
> 
> 
> 
> 
> 
> ----------------------------------------------------------------
> Philip Warner                    |     __---_____
> Albatross Consulting Pty. Ltd.   |----/       -  \
> (A.B.N. 75 008 659 498)          |          /(@)   ______---_
> Tel: (+61) 0500 83 82 81         |                 _________  \
> Fax: (+61) 03 5330 3172          |                 ___________ |
> Http://www.rhyme.com.au          |                /           \|
>                                   |    --________--
> PGP key available upon request,  |  /
> and from pgp.mit.edu:11371       |/