Integer Linear Programming with CVXPY in python3

Question

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 · Accepted Answer · 2019-05-16 19:07:15Z

6

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.

answered May 16, 2019 at 19:07

user3289556

1752 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Integer Linear Programming with CVXPY in python3

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related