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
florian@artemis:~$ cat /etc/*-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=10.04
DISTRIB_CODENAME=lucid
DISTRIB_DESCRIPTION="Ubuntu 10.04.1 LTS"
florian@artemis:~$ 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
florian@artemis:~$ 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(¶meters);
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, ¶meters);
}
florian@artemis:~$ gcc -lglpk bug.c
florian@artemis:~$ 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 ...
_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk
