The order of variables may affect the feasibility of the model
Awaiting user input
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!
-
Official comment
-
Gurobi Staff
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?. -
-
-
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,
Matthias0 -
Post is closed for comments.
Comments
2 comments