Possible bug in cvxopt.glpk.ilp ?

[Benjamin Sperisen]

Hi all,

In a project, I've calling the GLPK MIP solver through CVXOPT, but the solutions that are returned appear to be infeasible despite getting 'optimal' returned as the status. I put together a minimal working example using the MIP that arose in my application.

I've copied the code below for readability in this email, but it needs to be run alongside the text files in the zip attached, which contain the matrices/vectors for the problem I've included. Here's the code:

import numpy as np
from numpy import genfromtxt
import cvxopt, cvxopt.glpk

c = genfromtxt('c_file')
G = genfromtxt('G_file')
h = genfromtxt('h_file')
A = genfromtxt('A_file')
b = genfromtxt('b_file')
B_str_list = list(open('big_B_file').read().split())
B_set = set([int(ind) for ind in B_str_list])

status, x = cvxopt.glpk.ilp(cvxopt.matrix(c), cvxopt.matrix(G), cvxopt.matrix(h), cvxopt.matrix(A), cvxopt.matrix(b), I=set(), B=B_set)

print 'Status returned:', status
print 'This should be non-positive:', max(np.dot(G,x) - np.atleast_2d(h).T)

And here's the output:

GLPK Integer Optimizer, v4.57
54 rows, 26 columns, 110 non-zeros
12 integer variables, all of which are binary
Preprocessing...
40 rows, 26 columns, 96 non-zeros
12 integer variables, all of which are binary
Scaling...
 A: min|aij| =  8.004e-17  max|aij| =  2.000e+01  ratio =  2.499e+17
GM: min|aij| =  7.588e-05  max|aij| =  1.318e+04  ratio =  1.737e+08
EQ: min|aij| =  5.758e-09  max|aij| =  1.000e+00  ratio =  1.737e+08
2N: min|aij| =  5.372e-09  max|aij| =  1.531e+00  ratio =  2.850e+08
Constructing initial basis...
Size of triangular part is 40
Solving LP relaxation...
GLPK Simplex Optimizer, v4.57
40 rows, 26 columns, 96 non-zeros
      0: obj =  -4.589286805e+01 inf =   1.570e+01 (4)
      3: obj =   1.742973131e+01 inf =   1.788e-08 (0)
Warning: numerical instability (primal simplex, phase II)
      7: obj =   1.853838675e+01 inf =   0.000e+00 (0) 2
*    22: obj =  -2.319208708e+01 inf =   7.890e-09 (0) 2
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
+    22: mip =     not found yet >=              -inf        (1; 0)
+    28: >>>>>  -6.345827867e-01 >=  -1.478478334e+01        (5; 0)
+    39: >>>>>  -2.251726750e+00 >=  -5.268824151e+00 134.0% (5; 5)
+    39: mip =  -2.251726750e+00 >=     tree is empty   0.0% (0; 15)
INTEGER OPTIMAL SOLUTION FOUND
Status returned: optimal
This should be non-positive: [0.26474078]

Note that the output in the very last line is positive, indicating that one of the inequality constraints in Gx <= h is violated, so x is not a feasible solution.

This seems like a bug to me, but please let me know if there's anything I'm missing. I'd also be very grateful for any suggestions on how to get this working.

Thanks!

Ben

[Dima Pasechnik]

Did you try calling glpk with your input directly?
It most probably has little to do with cvxopt.