bug-glpk
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Regression between 4.61 and 4.65 for problems which can be preproces


From: Peter Cawley
Subject: Re: Regression between 4.61 and 4.65 for problems which can be preprocessed to almost nothing
Date: Mon, 13 Jul 2020 16:14:53 +0100

Hi Domingo,

Indeed I do have the original data, though it isn't particularly relevant. As background, my use-case involves solving millions of integer problems per day, every day. A high proportion of these problems are trivially solvable by GLPK, but GLPK is used because a small proportion of these problems really do require a clever solver. This use-case has been running without issue for years, until a recent library upgrade from 4.61 to 4.65, at which point lots of problems started failing every day. This particular "s.lp" example falls into the category of problems which are trivially solvable, but I'd still like to be able to throw it at GLPK, because there are much harder problems in the same family, and determining a-priori whether a problem from the family is "trivial" or "hard" is itself difficult.

Regards,
Peter

On Mon, Jul 13, 2020 at 3:59 PM Domingo Alvarez Duarte <mingodad@gmail.com> wrote:
Hello Peter !

Do you have the original model/data that was used to generate the "s.lp" ?

Maybe the problem is in the bad model generation instead.

Cheers !

On 13/7/20 15:25, Peter Cawley wrote:
> Hi all,
>
> The enclosed s.lp is solvable by GLPK 4.61:
>
> -----
> $ glpk-4.61/examples/glpsol --glp s.lp
> GLPSOL: GLPK LP/MIP Solver, v4.61
> Parameter(s) specified in the command line:
>  --glp s.lp
> Reading problem data from 's.lp'...
> 81 rows, 48 columns, 168 non-zeros
> 48 integer variables, none of which are binary
> 331 lines were read
> GLPK Integer Optimizer, v4.61
> 81 rows, 48 columns, 168 non-zeros
> 48 integer variables, none of which are binary
> Preprocessing...
> 1 row, 0 columns, 0 non-zeros
> 0 integer variables, none of which are binary
> Scaling...
>  A: min|aij| =  1.000e+00  max|aij| =  1.000e+00  ratio =  1.000e+00
> Problem data seem to be well scaled
> Solving LP relaxation...
> GLPK Simplex Optimizer, v4.61
> 1 row, 0 columns, 0 non-zeros
> ~     0: obj =   0.000000000e+00  infeas =  0.000e+00
> OPTIMAL SOLUTION FOUND
> Integer optimization begins...
> +     0: mip =     not found yet >=              -inf  (1; 0)
> +     0: >>>>>   0.000000000e+00 >= 0.000000000e+00   0.0% (1; 0)
> +     0: mip =   0.000000000e+00 >=     tree is empty 0.0% (0; 1)
> INTEGER OPTIMAL SOLUTION FOUND
> Time used:   0.0 secs
> Memory used: 0.1 Mb (80560 bytes)
> -----
>
> But causes an internal failure with GLPK 4.65:
>
> -----
> $ glpk-4.65/examples/glpsol --glp s.lp
> GLPSOL: GLPK LP/MIP Solver, v4.65
> Parameter(s) specified in the command line:
>  --glp s.lp
> Reading problem data from 's.lp'...
> 81 rows, 48 columns, 168 non-zeros
> 48 integer variables, none of which are binary
> 331 lines were read
> GLPK Integer Optimizer, v4.65
> 81 rows, 48 columns, 168 non-zeros
> 48 integer variables, none of which are binary
> Preprocessing...
> 1 row, 0 columns, 0 non-zeros
> 0 integer variables, none of which are binary
> Scaling...
>  A: min|aij| =  1.000e+00  max|aij| =  1.000e+00  ratio =  1.000e+00
> Problem data seem to be well scaled
> Solving LP relaxation...
> GLPK Simplex Optimizer, v4.65
> 1 row, 0 columns, 0 non-zeros
> ~     0: obj =   0.000000000e+00  infeas =  0.000e+00
> OPTIMAL SOLUTION FOUND
> Integer optimization begins...
> glp_add_cols: ncs = 0; invalid number of columns
> Error detected in file api/prob1.c at line 362
> Abort trap: 6
> -----
>
> According to LLDB, the call stack at the point of failure is:
>
> -----
>   * frame #0: 0x00007fff570acb66 libsystem_kernel.dylib`__pthread_kill
> + 10
>     frame #1: 0x00007fff57277080 libsystem_pthread.dylib`pthread_kill
> + 333
>     frame #2: 0x00007fff570081ae libsystem_c.dylib`abort + 127
>     frame #3: 0x0000000100105a7d
> libglpk.40.dylib`errfunc(fmt=<unavailable>) at error.c:55 [opt]
>     frame #4: 0x00000001000c03c9
> libglpk.40.dylib`glp_add_cols(lp=0x0000000100401b10, ncs=0) at
> prob1.c:362 [opt]
>     frame #5: 0x00000001000eab84 libglpk.40.dylib`_glp_ios_create_tree
> [inlined] _glp_ios_create_pool(tree=<unavailable>) at glpios01.c:1395
> [opt]
>     frame #6: 0x00000001000eab6a
> libglpk.40.dylib`_glp_ios_create_tree(mip=<unavailable>,
> parm=0x00007ffeefbff608) at glpios01.c:129 [opt]
>     frame #7: 0x00000001000e3eda
> libglpk.40.dylib`solve_mip(P=0x0000000100400f60,
> parm=0x00007ffeefbff608, P0=0x0000000100400310,
> npp=0x0000000100400080) at glpapi09.c:244 [opt]
>     frame #8: 0x00000001000e3d2c libglpk.40.dylib`glp_intopt [inlined]
> preprocess_and_solve_mip(P=<unavailable>) at glpapi09.c:415 [opt]
>     frame #9: 0x00000001000e391a
> libglpk.40.dylib`glp_intopt(P=<unavailable>, parm=0x0000000000000000)
> at glpapi09.c:634 [opt]
>     frame #10: 0x00000001000031d4 glpsol`main(argc=<unavailable>,
> argv=0x42773482f5d96a00) at glpsol.c:1423 [opt]
> -----
>
> Based on a very superficial understanding of the code, guarding the
> `glp_add_cols(pool, tree->mip->n);` call within `ios_create_pool` with
> `if (tree->mip->n)` seems to sidestep the failure, but perhaps a more
> involved fix is required.
>
> Regards,
> Peter
>


reply via email to

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