6

I'm trying to solve an integer linear programming problem using the CVXPY but am struggling with some syntax and can not figure out a way of how to enforce my variable that I'm interested to solve for the constraint to take values of either 0 or 1. I thought that setting it to be boolean was the solution in the Variable object, but for some reason I'm not getting what I want to

I installed the cvxpy library and tried to run it using a small example to solve it. The input for my problem is a binary matrix M of size (I, J) that only has values of (0 or 1), also the variable that I want to solve for is a boolean (or a binary vector again) vector P of size J,

the objective function is to minimize the sum of the values of my Variable vector of size J (i.e. minimize the number of 1s inside that vector)

such that sum of each row of my matrix M times my variable Vector P is greater or equal to 1. i.e. Summation(over j) of Mij*Pj >= 1, for all i.

with the objective of minimizing sum of vector P.

I wrote the following code to do that however I'm struggling in finding what is it that I did wrong in it.

import numpy as np
import cvxpy as cp

M = np.array([[1,0,0,0], [1,0,0,0], [0,1,1,0], [1,0,0,0], [0,0,1,1], [0,0,1,0]])

variable= cp.Variable(M.shape[1], value = 1, boolean=True)

one_vec = np.ones(M.shape[1])

obj = cp.Minimize(sum(np.dot(variable, one_vec)))

constraints = []

for i in range(len(M)):
    constraints.append(np.sum(np.dot(M[i], variable)) >= 1)

problem = cp.Problem(obj, constraints=constraints)

problem.solve()

so as an answer to this simple example given by the matrix M in my code, the answer should be such that variable vector's value should be [1, 0, 1, 0], since multiplying the vector [1, 0, 1, 0] with the matrix

[[1, 0, 0, 0]

[1, 0, 0, 0]

[0, 1, 1, 0]

[1, 0, 0, 0]

[0, 0, 1, 1]

[0, 0, 1, 0] ]

would give a value of at least 1 for each row.

But if I run this code that I have written, I'm getting a value that is a float as my answer, hence I'm doing something wrong which I cannot figure out. I do not know how to phrase this question programmatically I guess so that the solver would solve it. Any help would be well appreciated. Thanks.

user3289556
  • 155
  • 2
  • 11

1 Answers1

5

UPDATE! I think I figured it out

I modified the code to this:

import numpy as np
import cvxpy as cp

M = np.array([[1,0,0,1], [1,0,0,1], [0,1,1,1], [1,0,0,1], [0,0,1,1], [0,0,1,1]])

selection = cp.Variable(M.shape[1], boolean = True)
ones_vec = np.ones(M.shape[1])

constraints = []
for i in range(len(M)):
    constraints.append(M[i] * selection >= 1)

total_genomes = ones_vec * selection

problem = cp.Problem(cp.Minimize(total_genomes), constraints)

problem.solve()

and now it's working. I used the * operator instead of numpy dot product, cvxpy has overloaded that operator I think to perform vector multiplications.

user3289556
  • 155
  • 2
  • 11