RE: [Help-glpk] gplsol.exe 4.4.1 and vpm1.mps of MIPLib 3.0

[Robert Horvath]

The problem of glpk not stopping when the solution is optimal is not a bug!
Glpk uses heuristics to find optimal solution. This helps to find the
solutions faster, but its disadvantage is that it is not able to determine
quickly whether the solution it has provided is optimal or not.

So I guess you have to limit the iterations or set a timelimit.

Regards
Robert

> -----Original Message-----
> From: Cheng,Jen-Min [mailto:address@hidden
> Sent: 2004. április 27. 23:03
> To: 'Robert Horvath'
> Subject: RE: [Help-glpk] gplsol.exe 4.4.1 and vpm1.mps of MIPLib 3.0
> 
> 
> It did converge the the optimal solution psoted by MIPLib after about 6414
> iterations.  However it did not stop automatically.
> 
> Attached is a copy the glpsolexe, which has to be renamed to glpsol.exe,
> and
> vpm1.mps.
> 
> It is downloaded from
> http://sourceforge.net/project/showfiles.php?group_id=23617&package_id=565
> 42
> &release_id=228974
> 
> load_mps: name `VPM1'
> load_mps: 235 rows
> load_mps: 378 columns
> load_mps: 917 non-zeros
> load_mps: 1 right-hand side vector(s)
> load_mps: 0 range vector(s)
> load_mps: 1 bound vector(s)
> load_mps: 1247 cards were read
> lpx_adv_basis: size of triangular part = 235
> 
> +  3176: mip =  2.100000000e+001; lp =  1.541666667e+001 (240, 443)
> +  6464: mip =  2.000000000e+001; lp =  1.541666667e+001 (335, 1110)
> 
> + 90548: mip =  2.000000000e+001; lp =  1.541666667e+001 (3891, 13704)
> +100499: mip =  2.000000000e+001; lp =  1.541666667e+001 (3703, 14870)
> ITERATIONS LIMIT EXCEEDED; SEARCH TERMINATED
> 
> -----Original Message-----
> From: Robert Horvath [mailto:address@hidden
> Sent: Tuesday, April 27, 2004 12:25 PM
> To: 'Cheng,Jen-Min'; address@hidden
> Subject: RE: [Help-glpk] gplsol.exe 4.4.1 and vpm1.mps of MIPLib 3.0
> 
> 
> Your version must be faulty for some reason. Mine that was compiled by
> Visual Studio works just fine and it finds the optimal MIP solution after
> 775 iterations (although it continues to search for the MIP optimum). It
> is
> also version 4.4 of glpk.
> 
> 
> --------------------------------------------------------------------------
> --
> F:\rob\lp\glpk-4.4>glpsol.exe --mps vpm1.mps --wlpt k.lp -o k.out
> load_mps: reading LP data from `vpm1.mps'...
> load_mps: name `VPM1'
> load_mps: 235 rows
> load_mps: 378 columns
> load_mps: 917 non-zeros
> load_mps: 1 right-hand side vector(s)
> load_mps: 0 range vector(s)
> load_mps: 1 bound vector(s)
> load_mps: 1233 cards were read
> lpx_write_lpt: writing problem data to `k.lp'...
> lpx_simplex: original LP has 235 rows, 378 columns, 917 non-zeros
> lpx_simplex: presolved LP has 174 rows, 263 columns, 526 non-zeros
> lpx_adv_basis: size of triangular part = 174
>       0:   objval =  0.000000000e+000   infeas =  1.000000000e+000 (0)
>      39:   objval =  1.541666667e+001   infeas =  1.451271928e-018 (0)
> OPTIMAL SOLUTION FOUND
> Integer optimization begins...
> Objective function is integral
> +    39: mip =     not found yet; best =          none yet (1, 0)
> +   137: mip =  2.200000000e+001; best =  1.541666667e+001 (31, 32)
> +   179: mip =  2.100000000e+001; best =  1.541666667e+001 (43, 48)
> +   775: mip =  2.000000000e+001; best =  1.541666667e+001 (210, 277)
> +  6373: mip =  2.000000000e+001; best =  1.541666667e+001 (1332, 2247)
> + 10926: mip =  2.000000000e+001; best =  1.541666667e+001 (2581, 4078)
> --------------------------------------------------------------------------
> --
> 
> Regards
> Robert
> 
> > -----Original Message-----
> > From: address@hidden
> [mailto:help-
> > address@hidden On Behalf Of
> Cheng,Jen-
> > Min
> > Sent: 2004. április 27. 17:48
> > To: 'address@hidden'
> > Subject: [Help-glpk] gplsol.exe 4.4.1 and vpm1.mps of MIPLib 3.0
> >
> > Dear GLPK:
> >
> >     glpsol.exe 4.4.1 is tested using vpm1 of MIPLib 3.0.  The output
> > showed that glpsol.exe found the optimal solution at iterations 1629 and
> > glpsol.exe could not converge until more than 240,000 iterations.
> >
> >     Will any one please tell me how a convergence criteria can be set?
> >
> >     glpsol.exe found the integer optimal solution of vpm2 of MIPLib 3.0
> > after 88072 iterations adn could not converge to the LP optimal solution
> > after 5864409 iterations.
> >
> >     What can be implemented so taht glpsol can converge to the optimal
> > solution?
> >
> >     Thanks.
> >
> > Jimmy Cheng
> >
> >
> > _______________________________________________
> > Help-glpk mailing list
> > address@hidden
> > http://mail.gnu.org/mailman/listinfo/help-glpk