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)))
0
-
Official comment
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
cross-post on OR Stackexchange
0
Post is closed for comments.
Comments
2 comments