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

  • December 06, 2024 00:37

  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.