Search code examples
pythonsparse-matrixlinear-programminggurobiinteger-programming

Coverage matrix to covering constraints in Python Gurobi

Let C be a binary covering matrix for a set covering problem, and I want to convert this into the appropriate covering constraints in Gurobi. I've managed to get it to work using scipy.csr_matrix, but the process seems slow. I'm wondering if there's a more efficient way.

# Convert coverage to sparse matrix
csr_cover = csr_matrix(C.astype(bool))
cover_rows = np.split(csr_cover.indices, csr_cover.indptr)[1:-1]

# add facility coverages to the covering constraints
for i in range(numDemands):
    m.addConstr(quicksum(X[j] for j in range(numSites) if i in cover_rows[j]) >= 1)
Solution

  • This seems to work faster for building the constraints than the above approach:

    cover_rows = [np.nonzero(t)[0] for t in C]

for i in range(numDemands):
    m.addConstr(quicksum(X[j] for j in cover_rows[i]) >= 1)