Long runtime for ILP involving permutation matrix

Yui Ishihara

December 31, 2020 01:35 Edited

• 
• 

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

  

  Simranjit Kaur

  • Gurobi Staff

  June 23, 2025 03:02 Edited

  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?.
• 

  Matthias Miltenberger

  • Gurobi Staff

  January 04, 2021 15:30 Edited

  cross-post on OR Stackexchange

  0

Post is closed for comments.