Re: [Help-glpk] performance issue

[Andrew Makhorin]

On Wed, 2016-09-07 at 09:44 -0400, Joshua Friedman wrote:
> I am working on a bit integer program and my data has 45000 variables
> (see below). I am basically  just looking for a feasible solution, my
> objective is constant. 
> 
> 
> My question: it took 10 minutes to run using the glpk solver. I
> converted to a CBC form and it solved it in 1 minute, and using Gurobi
> it took about 1 second (but it used all 8 threads).  Am I doing
> something wrong with glpk for bit integer programs?  

Glpk mip solver is not perfect, sorry. It lacks many algorithmic
features that CBC and Gurobi have, so its performance is not very good,
especially for large mip instances.

> Is there an option that is more efficient?

You may try '--minisat' option.

> 
> Model has been successfully generated
> GLPK Integer Optimizer, v4.60
> 68514 rows, 45040 columns, 372605 non-zeros
> 45040 integer variables, all of which are binary
> Preprocessing...
> 9020 hidden covering inequaliti(es) were detected
> 1397 constraint coefficient(s) were reduced
> 15253 rows, 29410 columns, 161743 non-zeros
> 29410 integer variables, all of which are binary
> Scaling...
>  A: min|aij| =  1.000e+00  max|aij| =  1.000e+01  ratio =  1.000e+01
> Problem data seem to be well scaled
> Constructing initial basis...
> Size of triangular part is 15253
> Solving LP relaxation...
> GLPK Simplex Optimizer, v4.60
> 15253 rows, 29410 columns, 161743 non-zeros
>       0: obj =   0.000000000e+00 inf =   6.040e+02 (247)
>     500: obj =   0.000000000e+00 inf =   3.980e+02 (115) 1
>     837: obj =   0.000000000e+00 inf =   0.000e+00 (0) 1
> OPTIMAL LP SOLUTION FOUND
> Integer optimization begins...
> +   837: mip =     not found yet >=              -inf        (1; 0)
> +  1389: mip =     not found yet >=   0.000000000e+00        (30; 0)
> +  2309: mip =     not found yet >=   0.000000000e+00        (50; 7)
> +  2835: mip =     not found yet >=   0.000000000e+00        (77; 14)
> +  3106: mip =     not found yet >=   0.000000000e+00        (113; 14)
> 
> 
> -- 
> Joshua Friedman PhD
> 
> address@hidden
> http://www.math.sunysb.edu/~joshua
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/help-glpk