Long runtime for ILP involving permutation matrix

Yui Ishihara

2020年12月31日 01:35 編集済み

• 
• 

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

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2025年06月23日 03:02 編集済み

  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

  2021年01月04日 15:30 編集済み

  cross-post on OR Stackexchange

  0

投稿コメントは受け付けていません。