Sum equals sum constraint
Answered
Dear Gurobi-Team,
at the moment I am struggling with a flow conservation constraint I implemented for a complex vehicle routing problem. I hope that you might have a spark for the solution for me :-)
In general, I have arcs as tuples from i to j with associated times (e.g. ('New York', 5, 'Boston, 150, Truck1)).
My binary variable x is created with a set of all possible arcs/tuples including "staying" arcs, such as ('New York', 5, 'New York', 5, Truck1) and "1" indicates if an arc is used.
I now implemented a flow conservation constraint which should check, that the sum of all ingoing arcs to a node at a specific time equals the sum of all outgoing arcs at a specific time. My formulation is as follows:
m.addConstrs(
(x.sum('*', '*', i, t, k) == x.sum(i, t, '*', '*', k)
for k in trucks for i in nodes if (i != truckd["Truck" +str(k)][0] and i != truckd["Truck" +str(k)][1]) for t in range(expansion)), "C#4Flow")
Whereas the conditional part excludes origin and destination of the truck route because the flow won't hold for the initial origin if the truck leaves it when it was stationed there.
The problem I have is, that in the added constraints which I extract from the *.lp-file the constraint omits the "Staying arcs" and only adds arcs to the sums which are not leading to itself. Even though these variables exist as I checked.
Example from the *.ilp-file output of IIS:
C#4Flow[1, Boston, 39]: x[New York,0,Boston,39,1] - x[Boston,39,Portland,125,1] - x[Boston,39,Boston,40,1] = 0
Because of other constraints, this constraint can not hold. It would only hold if the value of x[Boston,39,Boston,39,1] would also be taken into account. I don't understand why it isn't added to the constraint even though I know it exists. (Boston is neither origin nor destination of the truck).
Can you perhaps help? Is the kind of formulation I used the reason?
Thanks in advance!
Best regards
-
The constraint for \( \texttt{i = 'Boston'} \), \( \texttt{t = 39} \), \( \texttt{k = 1} \) is:
x.sum('*', '*', 'Boston', 39, 1) == x.sum('Boston', 39, '*', '*', 1)
It seems to me that the variable \( \texttt{x['Boston', 39, 'Boston', 39, 1]} \) appears on both sides of this constraint with the same coefficient (\(1\)). Thus, Gurobi simplifies the constraint by removing the variable from both sides.
1 -
Thanks Eli!
Sometimes, one doesn't see the wood for the trees...
0
Please sign in to leave a comment.
Comments
2 comments