[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## Re: [Help-glpk] Small Integer Program takes long time to solve

**From**: |
Andrew Makhorin |

**Subject**: |
Re: [Help-glpk] Small Integer Program takes long time to solve |

**Date**: |
Mon, 21 Jul 2008 20:30:41 +0400 |

>* I have a small integer program whose optimal solution value is 49.*
>* Root relaxation is 48.5454. Since all the variables are integer, one*
>* expects it to stop when a solution with value 49 is found. Instead,*
>* GLPK takes a long time to converge.*
>* I also tried lp-solve, it found an optimal solution quickly (less*
>* than 0.1 second). Here is the output:*
>* Optimal solution 49 after 72 iter, 34 nodes *
>* (gap 0.0%).*
>* Value of objective function: 49*
>* Branch Bound depth: 18*
>* Nodes processed: 34*
>* Simplex pivots: 72*
>* Number of equal solutions: 1*
>* I don #39;t think lp-solve is doing anything particular. It did not*
>* generate cuts and just branched on the first fractional integer*
>* variable.*
>* An mps file is attached. I would appreciate if someone can explain why*
>* it is taking so long.*
Most probably lp_solve detects integrality of the objective that
helps it to finish the search once the gap becomes zero. A similar
feature was implemented in earlier versions of the glpk mip solver,
however, currently it is disabled due to some technical reasons.
I would like to note that your mip instance is hard, and there is
just a happy chance that the glpk solver (as well as lp_solve) finds
the optimum on the first try.