The order of variables may affect the feasibility of the model

ユーザーの入力を待っています。

Xinyi Hu

2021年11月27日 16:42

Hello, 

I am using gurobi to solve a TSP problem. I have 40 locations, based on several constraints, I will choose some of them to construct a round trip. So my decision variables are like:

X = model.addVars(
    40,
    40,
    vtype=GRB.BINARY,
    lb=0,
    ub=1,
    name=[f"Place {i}{Name[i]} to Place {j}{Name[j]}" for i in range(N) for j in range(N)],
)
P = model.addVars(40, vtype=GRB.BINARY, lb=0, ub=1, name=Name[0:40])
U = model.addVars(40, vtype=GRB.INTEGER, lb=1, ub=(N - 1), name=[f"u{i}" for i in range(N)])

P is a binary variable to see whether or not this location is chosen. X is the route and U avoids sub tour.

I suppose the following two constraints are the ones that caused my confusion:

model.addConstr(sum(P[i] for i in range(30,40))==1)
model.addConstr(sum(Fare[i]*P[i] for i in range(40)) <= Fare_Limit)

Fare is a given list and I have tried many times. When Fare[39] is larger than the Fare_Limit, then gurobi will run for a long time, and finally report model is infeasible. But if I remove the last variable, and run gurobi again, I will get a feasible solution. If I shuffle the list Fare, assuring the last one is no larger than the Fare_Limit, I will also get a feasible solution. It seems like gurobi just searches one of the branches, base on the Constraint sum(P[i] for i in range(30,40))==1, if it doesn't find a solution in that branch(P[39]==1), it stops.

When it reports infeasible, I tried to computeIIS(), but I wait for two hours, it continues printing, and I can't see which constraint leads to the infeasibility.

Any help is appreciated, thank you!

0

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

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

  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年11月29日 08:17

  Hi Xinyi,

  To model the TSP, you usually use callbacks to handle the subtours because a complete description of the problem is exponentially large. Please refer to our TSP example for a good starting point on how to do that: tsp.py

  I hope that helps.

  Cheers,
  Matthias

  0

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