Re: [Help-glpk] glpk and MIPLIB 2003

[Xypron]

Hello Cheng,

the MIP gap compares a solution with all integer variables fixed to an 
integer value with a lower bound solution where some integer variables 
are allowed to have non integer values. Only if the MIP gap is 0 you can 
be sure that the optimal solution has been reached.

If you find the optimum solution with a large MIP gap either you are 
lucky or the 2nd best solution is far away from the best solution. You 
cannot count on it.

In practical use it is often not necessary to find a mathematically 
optimal solution. A solution sufficiently close to the optimum will do. 
This is when the definition of a MIP gap to end the solution process 
comes in handy. For instance when solving a problem involving storage 
cost and setup costs in a production process you might be happy if the 
gap is less then 1 % of the storage cost because many parameters like 
demand are not exactly known anyway.

When choosing a MIP gap you have to decide how good a solution you need.

Best regards

Xypron


Cheng,Jen-Min wrote:
> MIPLIB 2003 _http://miplib.zib.de/_
>
> I compiled the glpk 4.31 with Microsoft Visual Studio 2005.
>
> Glpk can solve manna81.mps of MIPLIB 2003 with –mipgap 1.0 in about 37 
> seconds. –mipgap 0.05 ended with tree is empty after about 129138 seconds.
>
> The two examples make me wonder how an appropriate mipgap can be 
> selected. In the first example, --mipgap 1.0 works. In the second 
> exmple, --mipgap 0.05 could not converge to the psoted solution.
>
> Will you please provide guidelines for selecting mipgap. Thanks.
>
> manna81.mps
>
> MIPLIB 2003
>
> http://miplib.zib.de/
>
> INT OBJ = -13164 LP OBJ=-13297
>
> 6480 Rows, 3321 Columns, 12960 Non-zeros
>
> 3303 Integers 18 Binaries
>
> --mipgap 1.0
>
> + 5184: mip = -1.316400000e+004 >= -1.329700000e+004 1.0% (285; 0)
>
> Time used: 36.6 secs
>
> However glpk with –mipgap 0.1 could not converge to the solution 
> posted by MIPLIB 2003.
>
> vpm2.mps
>
> MIPLIB 2003
>
> http://miplib.zib.de/
>
> INT OBJ = 13.75 LP OBJ=9.8892646
>
> 234 Rows, 378 Columns, 1085 Nonzeros
>
> 168 Binaries, 210 Continuos variables
>
>
> --mipgap 1.0
>
> + 2369: mip = 1.700000000e+001 >= 1.070274874e+001 37.0% (502; 45)
>
> Time used: 0.7 secs
>
> --mipgap 0.5
>
> + 2369: mip = 1.700000000e+001 >= 1.070274874e+001 37.0% (502; 45)
>
> Time used: 0.7 secs
>
> --mipgap 0.3
>
> + 29961: mip = 1.525000000e+001 >= 1.156433411e+001 24.2% (6352; 680)
>
> Time used: 10.2 secs
>
> --mipgap 0.2
>
> + 33900: mip = 1.450000000e+001 >= 1.161038594e+001 19.9% (6720; 1581)
>
> Time used: 9.5 secs
>
> --mipgap 0.1
>
> +1462797: mip = 1.375000000e+001 >= 1.282598934e+001 6.7% (257981; 57219)
>
> Time used: 2630.4 secs
>
> --mipgap 0.05
>
> +1462797: >>>>> 1.375000000e+001 >= 1.282598934e+001 6.7% (257981; 57219)
>
> +6072379: mip = 1.375000000e+001 >= 1.373563363e+001 0.1% (2431; 
> +6074797: mip = 1.375000000e+001 >= tree is empty 0.0% (0; 1940503)
>
> Time used: 129138.0 secs
>
>
>
>
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/help-glpk
>