Re: [Help-glpk] GLPK just hangs

[glpk xypron]

Hello Manish,

the line
+ 73068: mip = -5.000000000e-001 <= -2.500000000e-001  50.0% (107; 10024)
says that 10024 nodes in the branch-and-bound tree have been rejected,
107 unexplored nodes are still in the tree that could possibly lead to an
improved MIP solution. The best solution up to now is -.5. There can
be no better solution then -.25. This results in a gap of 50 %. The number
of simplex iterations is 73068.

Obviously GLPK is not in an infinite loop but still exploring the
tree. Looking at the ratio of open nodes to fathomed nodes, could it be
that in your program you are using a depth first search (which often
is not performing well)? Are you using the same search strategy when
solving the file you have written to disk?

Please, state the branch heuristic and the backtracking methods used
in both cases. It would be helpful to be able to look at the LP file.

lpx_simplex and lpx_integer are deprecated functions. doc/glpk.pdf
describes how to set the search strategy and the branching heuristic
when using the current API.

The default settings used by glpsol are
* branch using heuristic by Driebeck and Tomlin
* backtrack using node with best local bound

Best regards

Xypron





-------- Original-Nachricht --------
> Datum: Thu, 2 Sep 2010 15:25:31 -0700
> Von: Manish Jain <address@hidden>
> An: address@hidden
> Betreff: [Help-glpk] GLPK just hangs

> Hello all,
> 
> I have a cut/column generation implementation using GLPK 4.44 in Java.
> I am seeing some weird behavior when I increase the problem size.
> Glpk just gets stuck in an infinite loop every time after 42 iterations in
> my case. The problem size is big here (details in the attachment).
> 
> The weirdness is not that it just gets stuck in an infinite loop. The
> weird
> part is that it works fine if instead of calling lpx_simplex/lpx_integer
> on
> the problem that is already in memory, I write the problem to a file and
> load it again.
> i.e.
> lpx_simplex(lp);
> lpx_integer(lp) <- Glpk gets stuck. There is no discernible error message.
> Output log attached.
> 
> lpx_write_cpxlp(lp, fileName)
> lpx_delete_prob(lp)
> lp = lpx_create_prob()
> lp = lpx_read_cpxlp(fileName)
> lpx_simple(lp);
> lpx_integer(lp); <- Works and gives the solution in about 2 seconds
> 
> Additionally, if I write the problem to a file when it gets stuck, then I
> can solve it with glpsol --lp fileName in a matter of 2 secs without any
> troubles as well.
> 
> Any ideas, anyone?
> Also, can anyone explain to me the meaning of various lines of GLPK
> output,
> e.g.:
> + 49135: mip = -5.000000000e-001 <= -2.500000000e-001  50.0% (46; 6967)
> Are these: [Iteration No] [Problem Class] [... ?] ( ...; row-No)
> 
> I am using GLPK-4.44 Java bindings.
> The code is all in Java.
> Output log is attached.
> 
> Thanks.
> 
> Manish Jain
> University of Southern California

-- 
GMX DSL SOMMER-SPECIAL: Surf & Phone Flat 16.000 für nur 19,99 Euro/mtl.!*
http://portal.gmx.net/de/go/dsl