Re: [Help-glpk] Stack overflow during column generation

[Andrew Makhorin]

> I am using glpk 4.17 with Visual Studio 8.0 (2005).  GLPK is implemented
> as a DLL.  The lp solver is called repeatedly in a standard column 
> generation schema.  The generation of the columns does not involve 
> GLPK.  GLPK is used to solve the lp master problem, which gets bigger in
> every generation.  The main work is done by set_mat_col and lpx_simplex.
> The column generation works perfectly for small problem instances.
> Originally experienced stack overflow catastrophic error around 1800
> columns with 1 MB of stack memory.
> The advice of glpk developers was to increase the stack size to remedy
> the problem.
> Increased stack size to 2 and then to 4 MB.  Now the error occurs at
> about 9000 columns.
> However, glpsol compiled with a stack size of 1 MB can read this problem
> both in lp and free mps format and solve the problem quickly.  glpsol
> uses the same glpk DLL.
> The next few lines are the log from glpsol for the 44 iteration.   
> During the 45 iteration the column generation schema has the stack 
> overflow error.

> lpx_read_freemps: reading problem data from `eilon5180044.mps'...
> lpx_read_freemps: problem Eilon5180
> lpx_read_freemps: 53 rows, 8981 columns, 133346 non-zeros
> lpx_read_freemps: 69027 records were read
> lpx_simplex: original LP has 53 rows, 8981 columns, 133346 non-zeros
> lpx_simplex: presolved LP has 51 rows, 8980 columns, 124366 non-zeros
> lpx_adv_basis: size of triangular part = 50
>       0:   objval =  7.605445426e+003   infeas =  1.000000000e+000 (1)
>      91:   objval =  6.877951512e+003   infeas =  0.000000000e+000 (0)
> *    91:   objval =  6.877951512e+003   infeas =  0.000000000e+000 (0)
> *   200:   objval =  5.856679007e+003   infeas =  0.000000000e+000 (0)
> *   270:   objval =  5.766210960e+003   infeas =  1.184569440e-015 (0)
> OPTIMAL SOLUTION FOUND
> Time used:   1.0 secs
> Memory used: 15.0 Mb (15769400 bytes)

> What is the difference in the memory management between those two ways
> of using GLPK (monolithic versus column generation)?  What can I do to
> make my program manage memory like glpsol so that larger problems can be
> solved?  Do I need to call a memory clean-up routine at the end of every
> iteration?

All glpk routines (except parsing and evaluating routines in the
MathProg translator) are not recursive, so the problem must be (if
it is) only in the glpk dll.

Try to use the glpk static library rather than dll. Try also to
inspect your code more carefully. Are you using automatic arrays or
arrays allocated by alloca whose size depend on the problem size?
Are you using any non-documented glpk routines? Any callback or
recursive routines?

> By the way, the stack overflow is non-trappable and non-recoverable hard
> crash error, the application is immediately shut down by the operating
> system without any error message from either GLPK, my application, or
> the operating system.