[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: Jian Ye
Subject: Re: [Help-glpk] Small Integer Program takes long time to solve
Date: Mon, 21 Jul 2008 15:38:02 -0400

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.


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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]