[Help-glpk] problem with simple MIP

[Florian Widmann]

Hello,

I tried to use glpk to get a solution for the following almost trivial
MIP "feasibility" problem

1 <= 2*x_1 + 3*x_2 - 2*x_3 - 3*x_4 (x_i non-negative integers)

but the solver didn't finish within 15h. Changing the coefficient of x_4
from -3 to -1, -2, -4, or -5 gives (correct) solutions immediately. I'm
a bit puzzled now. It would be great if anyone could enlighten me?

See below for more information. I'm happy to provide more details if needed.

Thanks,
Florian


address@hidden:~$ cat /etc/*-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=10.04
DISTRIB_CODENAME=lucid
DISTRIB_DESCRIPTION="Ubuntu 10.04.1 LTS"
address@hidden:~$ uname -a
Linux artemis.doc.ic.ac.uk 2.6.38.2 #3 SMP Wed Mar 30 14:19:08 BST 2011
x86_64 GNU/Linux
address@hidden:~$ cat bug.c
#include <stdio.h>
#include "glpk.h"

int main (int argc, char *argv[]){
        int i;
        double ar[100+1];
        int ia[100+1], ja[100+1];
        glp_prob *problem = glp_create_prob();
        glp_iocp parameters;
        printf("\nGLPK version is %s\n\n", glp_version());
        glp_init_iocp(&parameters);
        parameters.presolve = GLP_ON;
        glp_add_rows(problem, 1);
        glp_add_cols(problem, 4);
        glp_set_row_bnds(problem, 1, GLP_LO, 1.0, 0.0);
        for(i = 1; i <= 4; i++){
                glp_set_col_kind(problem, i, GLP_IV);
                glp_set_col_bnds(problem, i, GLP_LO, 0, 0);
        }
        for(i = 1; i <= 4; i++){
                ia[i] = ((i-1)/4) + 1;
                ja[i] = ((i-1)%4) + 1;  
        }
        ar[1] = 2.0;
        ar[2] = 3.0;
        ar[3] = -2.0;
        ar[4] = -3.0;
        glp_load_matrix(problem, 4, ia, ja, ar);
        glp_intopt(problem, &parameters);
}
address@hidden:~$ gcc -lglpk bug.c
address@hidden:~$ a.out

GLPK version is 4.38

ipp_basic_tech:  0 row(s) and 0 column(s) removed
ipp_reduce_bnds: 1 pass(es) made, 0 bound(s) reduced
ipp_basic_tech:  0 row(s) and 0 column(s) removed
ipp_reduce_coef: 1 pass(es) made, 0 coefficient(s) reduced
glp_intopt: presolved MIP has 1 row, 4 columns, 4 non-zeros
glp_intopt: 4 integer columns, none of which are binary
Scaling...
 A: min|aij| =  2.000e+00  max|aij| =  3.000e+00  ratio =  1.500e+00
Problem data seem to be well scaled
Crashing...
Size of triangular part = 1
Solving LP relaxation...
*     0: obj =   0.000000000e+00  infeas =  0.000e+00 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+     0: mip =     not found yet >=              -inf        (1; 0)
+  9013: mip =     not found yet >=   0.000000000e+00        (9015; 0)
+ 12048: mip =     not found yet >=   0.000000000e+00        (12050; 0)
+ 14135: mip =     not found yet >=   0.000000000e+00        (14137; 0)
+ 15746: mip =     not found yet >=   0.000000000e+00        (15748; 0)
+ 17163: mip =     not found yet >=   0.000000000e+00        (17165; 0)

... and so on for hours ...