How to properly implement constraints with more than two "equal"-operators in Python
AnsweredDear community,
my problem isn't as much about how to implement a constraint when there's more than one equal-operator - because this isn't too hard to do and can be found in this forum - it's more about how to do it properly because apparently I'm doing something wrong.
The constraint I'm trying to implement is the following:
Where x(ijk) is 1 if vehicle k travels from i to j and 0 if not. y(ik) is 1 if node i is visited by vehicle k and 0 if not.
My implementation is as follows: (I'm just putting the range for k intentionally high because the amount of vehicles is unlimited and I don't this part to interfere with the rest of the code)
for i in V:
for k in range(20):
if (i, j, k) in x:
cons2l = m.addConstr(quicksum(x[i, j, k] for j in V if i != j) == y[i, k], name="cons2l %s" % i)
cons2r = m.addConstr(quicksum(x[j, i, k] for j in V if i != j) == y[i, k], name="cons2r %s" % i)
I'll also add another constraint, just in case my problem doesn't lie in the above constraint but instead in the following:
which I have implemented as
for i in K:
cons4 = m.addConstr(quicksum(y[i, k] for k in K) <= 1, name="cons4 %s" % i)
Where K is a set of all nodes, excluding the first (distribution center) because of course, this one can and usually needs to be visited more than once.
I implemented the decision variables as:
for i in V:
for k in K:
y[i, k] = m.addVar(vtype=GRB.BINARY, name=f"y[{i},{k}]")
for (i, j, k) in T: #T is just a set that includes all possible combinations of x(i, j, k). This could also be done by just doing 3 for-loops
x[i, j, k] = m.addVar(vtype=GRB.BINARY, name=f"x[{i},{j},{k}")
Now, in theory, this shouldn't be too complicated. Constraint 1 makes sure that if a vehicle visits node i, it also needs to leave node i and if this happens, the decision variable y(i,k) equals 1. This in combination with the second constraint should then ensure that no other vehicle ever visits node i because if this where to happen, the quicksum of y(i,k) should be 2 (or however often it's visited) and thus make the second constraint illegal.
However, this doesn't seem to happen. I had all the decision variables set to 1 printed out and they are as follows:
<gurobi.Var x[0,4,5 (value 1.0)>
<gurobi.Var x[4,0,5 (value 1.0)>
<gurobi.Var x[4,5,3 (value 1.0)>
<gurobi.Var x[5,4,3 (value 1.0)>
<gurobi.Var y[0,5] (value 1.0)>
<gurobi.Var y[4,2] (value 1.0)>
<gurobi.Var y[5,3] (value 1.0)>
And honestly, this just confuses me. y[4,2] is 1, even though vehicle 2 doesn't visit node 4? On the other hand, plenty of y-variables are 0 for nodes i, even though certain vehicles visited them, according to the x-variables. Two vehicles visit node 4, even though the quicksum of all y[4,i] is 1?
There seems to be something fundamentally wrong with this part of my setup but I really can't figure out what exactly it is and I've been struggling to find the fault in this for hours now.
Hence, I'm genuinely grateful for any kind of help. Thanks a million in advance.
All the best
-
Hi An,
Usually debugging such an issue can be done by writing out the model to a human-readable LP file.
model.write("myModel.lp")
You can open the generated file with any standard text editor. There you should check, whether the constraints of interest actually look as expected. This should be a good start to find the source of the issue.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
1 comment