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!
-
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
Please sign in to leave a comment.
Comments
1 comment