[Help-glpk] Need explanation for a terminal output

[Patrik Dufresne]

Hi,

While solving a MIP problem, I got the following terminal output and I
need help to interpret it. See my comments below.

> GLPK Integer Optimizer, v4.47
> 3781 rows, 26950 columns, 90897 non-zeros
> 26950 integer variables, 26680 of which are binary
> Preprocessing...
> 3520 rows, 25184 columns, 84631 non-zeros
> 25184 integer variables, all 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
> Constructing initial basis...
> Size of triangular part = 3520
> Solving LP relaxation...
> GLPK Simplex Optimizer, v4.47
> 3520 rows, 25184 columns, 84631 non-zeros
>   16213: obj =   0.000000000e+00  infeas =  3.870e+02 (0)
>   16500: obj =   0.000000000e+00  infeas =  3.810e+02 (0)
>   17000: obj =   0.000000000e+00  infeas =  3.480e+02 (0)
>   17500: obj =   0.000000000e+00  infeas =  2.980e+02 (0)
>   18000: obj =   0.000000000e+00  infeas =  2.540e+02 (0)
>   18500: obj =   6.500000000e+00  infeas =  2.290e+02 (0)
>   19000: obj =   1.200000000e+01  infeas =  1.730e+02 (0)
>   19500: obj =   1.075000000e+01  infeas =  1.260e+02 (0)
>   20000: obj =   8.000000000e+00  infeas =  1.040e+02 (0)
>   20500: obj =   1.100000000e+01  infeas =  7.825e+01 (0)
>   21000: obj =   1.250000000e+01  infeas =  7.150e+01 (0)
>   21500: obj =   1.333333333e+01  infeas =  6.083e+01 (0)
>   22000: obj =   1.064864865e+01  infeas =  4.914e+01 (0)
>   22500: obj =   1.119493671e+01  infeas =  1.729e+01 (0)
> * 22919: obj =   1.431795314e+01  infeas =  2.932e-15 (0)
> * 23000: obj =   9.703296703e+00  infeas =  7.096e-15 (0)
> * 23500: obj =   2.714285714e+00  infeas =  2.817e-14 (0)
> * 23721: obj =   1.000000000e+00  infeas =  1.486e-12 (0)
> OPTIMAL SOLUTION FOUND

As I understand, at this point the simplex algorithm is done finding
an optimal solution for my problem. The objective value found is 1.
>From this point, I'm expecting the branch-and-bound algorithm to
start.

> Integer optimization begins...
> + 23721: mip =     not found yet >=              -inf        (1; 0)
> | 34000: obj =   1.000000000e+00  infeas =  1.058e-12 (0)

Reading the GLPK documentation the symbol "|" means the dual simplex
algorithm is running. Why are we running simplex again? I'm expecting
the branch-and-bound to run or the Fpump heuristic since I enabled it.

> | 34500: obj =   1.000000000e+00  infeas =  6.092e-12 (0)
> | 35000: obj =   1.000000000e+00  infeas =  7.244e-12 (0)
> | 35500: obj =   1.000000000e+00  infeas =  3.837e-12 (0)
> | 36000: obj =   1.000000000e+00  infeas =  5.162e-12 (0)
> | 36500: obj =   1.000000000e+00  infeas =  2.919e-12 (0)
> | 37000: obj =   1.000000000e+00  infeas =  3.240e-12 (0)
> | 37500: obj =   1.000000000e+00  infeas =  2.045e-12 (0)
> | 38000: obj =   1.000000000e+00  infeas =  4.419e-12 (0)
> | 38500: obj =   1.000000000e+00  infeas =  8.190e-13 (0)
> | 39000: obj =   1.000000000e+00  infeas =  3.498e-12 (0)
> | 39500: obj =   1.000000000e+00  infeas =  1.208e-24 (0)
> | 40000: obj =   1.000000000e+00  infeas =  4.321e-12 (0)
> | 40500: obj =   1.000000000e+00  infeas =  5.864e-12 (0)
> | 41000: obj =   1.000000000e+00  infeas =  1.950e-13 (0)
> | 41500: obj =   1.000000000e+00  infeas =  3.029e-12 (0)
> | 42000: obj =   1.000000000e+00  infeas =  1.799e-12 (0)
> | 42500: obj =   1.000000000e+00  infeas =  4.196e-12 (0)
> | 43000: obj =   1.000000000e+00  infeas =  1.802e-12 (0)
> | 43500: obj =   1.000000000e+00  infeas =  1.449e-12 (0)
> | 44000: obj =   1.000000000e+00  infeas =  3.356e-12 (0)
> | 44500: obj =   1.000000000e+00  infeas =  4.529e-13 (0)
> | 45000: obj =   1.000000000e+00  infeas =  2.765e-12 (0)
> | 45500: obj =   1.000000000e+00  infeas =  2.123e-12 (0)
> | 46000: obj =   1.000000000e+00  infeas =  1.775e-12 (0)
> | 46500: obj =   1.000000000e+00  infeas =  4.873e-12 (0)
> | 47000: obj =   1.000000000e+00  infeas =  6.158e-12 (0)
> | 47500: obj =   1.000000000e+00  infeas =  2.211e-12 (0)
> | 48000: obj =   1.000000000e+00  infeas =  6.426e-12 (0)
> | 48500: obj =   1.000000000e+00  infeas =  1.391e-11 (0)
> | 49000: obj =   1.000000000e+00  infeas =  3.064e-12 (0)
> | 49500: obj =   1.000000000e+00  infeas =  2.130e-11 (0)
> | 50000: obj =   1.000000000e+00  infeas =  1.447e-12 (0)
> | 50500: obj =   1.000000000e+00  infeas =  6.791e-12 (0)
> | 51000: obj =   1.000000000e+00  infeas =  3.456e-12 (0)
> | 51500: obj =   1.000000000e+00  infeas =  9.451e-13 (0)
> | 51714: obj =   1.000000000e+00  infeas =  2.042e-13 (0)
> Applying FPUMP heuristic...
> Pass 1
> Solution found by heuristic: 1
> + 51714: mip =   1.000000000e+00 >=     tree is empty   0.0% (0; 1)
> INTEGER OPTIMAL SOLUTION FOUND

Patrik Dufresne