Long runtime for ILP involving permutation matrix
I am trying to solve the linear program in the snapshot. It is a very straightforward integer linear program.
My implementation is the following, where I am trying to find P (the X in the snapshot).
model = gp.Model()
C = calc_cost_matrix(n, A, R, attention, relevance)
P = model.addVars(n, n, vtype=GRB.BINARY)
obj = sum([C[i, j] * P[i, j] for i in range(n) for j in range(n)])
constrLHS = sum([calc_probabalistic_dcg_matrix(relevance, k=ndcgK)[i, j] * P[i, j]
for i in range(n) for j in range(n)])
model.setObjective(obj, GRB.MINIMIZE)
model.addConstr(constrLHS >= theta * calc_dcg(perfectRelevance, k=ndcgK))
model.addConstrs((P.sum("*", i) == 1 for i in range(n)))
model.addConstrs((P.sum(i, "*") == 1 for i in range(n)))
model.optimize()
However, compared with my similar implementation in cvxpy, which employs same Gurobi solver. This implementation is much slower.
As cvxpy adds another layer of abstraction, I am expecting that directly interacting with Gurobi through gurobipy should gives my speedier solving process. But this does not seem to be true.
I am suspecting constraint for permutation matrix (the following two lines) is the bottleneck, but I am not sure how to optimize this part.
model.addConstrs((P.sum("*", i) == 1 for i in range(n)))
model.addConstrs((P.sum(i, "*") == 1 for i in range(n)))

crosspost on OR Stackexchange
Please sign in to leave a comment.
Comments
1 comment