How can I code a binary integer linear programming?

[cristobal lopez silla]

Hi! I'm trying to code a problem but I don't understand a lot of things because i don't speak english. I want to code this problem:

max Z = 3x1+2x2-5x3-2x4+3x5

s.a.
  x1+x2+x3+2x4+x5 <= 4
  7x1+3x3-4x4+3x5 <= 8
  11x1-6x2+3x4-3x5 >= 3
  xj are all binaries

I've written this python code:

from cvxopt import glpk
from cvxopt.base import matrix as m


c = m([-3., -2., 5., 2., -3.])
A = m([[1., 1., 1., 2., 1.], [7., 0., 3., -4., 3.], [11., -6., 0., 3., -3.]])
b = m([4., 8., 3.])
binVars = range(len(b))
print(binVars)
sol = glpk.ilp(c, A, b, I=set(binVars), B=set(binVars))
print(sol[0])
print(sol[1])
print(sol)

 I have got the next error message:

Traceback (most recent call last):
  File "/home/tobal/ProgramasPython3/proglinenterabinaria2.py", line 10, in <module>
    sol = glpk.ilp(c, A, b, I=set(binVars), B=set(binVars))
ValueError: incompatible dimensions

Please, can someone write to me the right code?
Thanks

[Trish Gillett]

I haven't tried to used glpk for integer programs before, so I can't comment on that part of your code.  I do know why the current error is happening, though.
This error is occurring because the dimensions of A and b don't match.
The cvxopt matrix structure defines matrices based on their columns, and this is different from some other packages and languages like numpy, scipy, or matlab which define matrices based on rows.
For example, the matrix
[1 2 3 4]
[5 6 7 8]
would be written as [[1, 2, 3, 4], [5, 6, 7, 8]] in numpy, but is written as [[1, 5], [2, 6], [3, 7], [4, 8]] when using cvxopt's matrix structure.

This means that your code A = m([[1., 1., 1., 2., 1.], [7., 0., 3., -4., 3.], [11., -6., 0., 3., -3.]]) defines a matrix with 5 rows and 3 columns, and therefore A is incompatible with b because b only has 3 rows.

In this case, you should change A's definition to A = m([[1, 7, 11], [1, 0, -6], [1, 3, 0], [2, -4, 3], [1, 3, -3]]) and try your code again..

[cristobal lopez silla]

Ok, thanks with your help i obtain the solution. Here's the code:

from cvxopt import glpk
from cvxopt.base import matrix as m

c = m([-3., -2., 5., 2., -3.])

A = m([[1., 7., -11.], [1., 0., 6.], [1., 3., 0.], [2., -4., -3.], [1., 3., 3.]])
b = m([4., 8., -3.])
binVars = range(len(b) + 2)

sol = glpk.ilp(c, A, b, I=set(binVars), B=set(binVars))
print(sol[0])
print(sol[1])
print(sol)

How can I print the optimal value is 5 with Python?

Thanks

[Trish Gillett]

It seems that this solve function only returns a solve status and the solution, but not the optimal value achieved by the solution.  To recalculate the optimal value, you can take c and your solution vector x and compute c^Tx.  Remember that when your original problem was a maximization problem and cvxopt does minimization.  You changed your objective from max c^Tx to min -c^Tx, and this means that you need to multiply the objective value by -1 again to get the optimal value for the original problem.

Here's a little code to do those things:
## Let's give the optimal solution a name to make this easier to understand.
x = sol[1]
## c.T gives the transpose of c for cvxopt matrices.
## c.^Tx will give you the optimal solution to the problem you solved, but you have to add a negative sign to get the optimal value of your original maximization problem.
## Lastly, if you calculate -c.T*x you'll notice that the result is a 1x1 matrix because when you multiply a matrix by a matrix you get another matrix.  Since we really just want the number, we'll extract the element from the matrix by applying [0] to the multiplication result.  In other words:
optval = (-c.T*x)[0]
## And if you want to print it in a pretty sentence:
print "The optimal value is {0}".format(optval)

I explained it like that for readability, but you can do everything on one line with:
print "The optimal value is {0}".format((-c.T*sol[1])[0])

One last note: if you want to solve problems that might not have an optimal solution (ones that might be unbounded or infeasible),you should test if the solution status is optimal first:
if sol[0]=='optimal':

    print "The optimal value is {0}".format((-c.T*sol[1])[0])

else:

    print "The problem did not return an optimal solution. The solve status was {0}".format(sol[0])

-Trish

[cristobal lopez silla]

Wow, thank you very much for your help, it works fine.