Long runtime for ILP involving permutation matrix

Follow

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

• 

  Matthias Miltenberger

  • January 04, 2021 15:30
  • Edited

  cross-post on OR Stackexchange

  0

  Comment actions Permalink

Please sign in to leave a comment.