Re: Regression between 4.61 and 4.65 for problems which can be preprocessed to almost nothing

[Domingo Alvarez Duarte]

Hello !

In my opinion the fix for this problem could be here in 
"src/draft/glpapi09.c" (see patch bellow) because doesn't seem to make 
sense go forward if the presolved/preprocessed problem has zero rows or 
zero columns, another possibility is a bad (generated) problem and if 
that is the case the fix should be in detecting the bad problem.

=====

@@ -324,11 +324,11 @@ static int preprocess_and_solve_mip(glp_prob *P, 
const glp_iocp *parm)
       /* build transformed MIP */
       mip = glp_create_prob();
       npp_build_prob(npp, mip);
       /* if the transformed MIP is empty, it has empty solution, which
          is optimal */
-      if (mip->m == 0 && mip->n == 0)
+      if (mip->m == 0 || mip->n == 0)
       {  mip->mip_stat = GLP_OPT;
          mip->mip_obj = mip->c0;
          if (parm->msg_lev >= GLP_MSG_ALL)
          {  xprintf("Objective value = %17.9e\n", mip->mip_obj);
             xprintf("INTEGER OPTIMAL SOLUTION FOUND BY MIP PREPROCESSOR"

=====

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