[Bug-glpk] strange behaviour

[Andrew Makhorin]

In b&b the solution time highly depends on the order of branching,
i.e. on the order, in which variables with fractional values are
chosen to branch on. In particular, by default glpk b&b solver chooses
an integer/binary variable, whose value in current solution is
fractional and which being set on its integral bound involves greatest
degradation (worsening) of the objective (Driebeck-Tomlin's heuristic)
in order to fathom the corresponding branch as soon as possible.
However, in your problem the objective is zero (i.e. the problem is
integer feasibility) that makes all fractional variables equivalent to
be chosen, due to that the first appropriate varaible is always chosen.
Thus, changing the order of variables in the problem you change the
order of branching. I'm sure that the order of variable in the problem
instance built within Java example and in the lp file is different.

As to cplex, I think this was simply happy chance that glpk beat it :+)


Andrew Makhorin


--- Original message ---
From: <address@hidden>
To: bug-glpk <address@hidden>
Cc: mao <address@hidden>
Subject: strange behaviour
Date: Wednesday, April 30, 2003 6:06 PM

I was playing with the java porting of glpk and tried the example provided along
with N=5;
the author warned the it would take about 5 minutes.
to my surprise it took only 1 minute to be solved.
To be sure of the result I exported the file in .lp format and run it with 
glpsol
and this time it took about 5 minutes!!
Then I tried to solve it with CPLEX and it took about 6 minutes if I set
the emphasis on feasibility, otherwise (emphasis on optimality) it
runs for hours without finding the solution.

Beside the cplex experiments, why is that that the time is different when 
launched from within the java porting or from glpsol?
I checked in the java code and it looks like there are no special parameter 
settings.

Best regards,

 Ivan Luzzi

PS attached is a log and the file square.lp