Thanks for the reply. lp-solve did skip all the branch and bound nodes immediately after a solution with the optimal objective value was found. I have not found the code yet where it checks the integrality of the objective function. I will add some continuous variables to the objective function and test again.
The model is from bin packing. But it is formulated by generating all packing patterns (less than 100) as integer variables. So lp relaxation is pretty tight. Formulated naively where x_ij is the number of ith object assigned to bin j, Cplex could not find a feasible solution.
Thanks,
John
On Mon, Jul 21, 2008 at 12:30 PM, Andrew Makhorin <
address@hidden> wrote:
> 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.