Expression that requires serving both Nodes or not serving either Node

[GuyBenhaim]

I'd like Node B to be visited later than Node A (not necessarily immediately after) and, if either A or B cannot be served - skip visiting both A and B.

Applying just the time constraint works fine and Solver finds a solution and visits both (a simple case with only two Nodes):

model.solver().Add(model.CumulVar(model.NodeToIndex(A), "time") <= model.CumulVar(model.NodeToIndex(B), "time"));

But, when I add the "both or either" condition, no solution is found:

model.solver().Add(model.ActiveVar(model.NodeToIndex(A)) == model.ActiveVar(model.NodeToIndex(B)));

Do I really need the second condition? Any tips?

[GuyBenhaim]

Any comments?

[vbezuglyy]

Just to throw my two cents on this issue, I, as a user of or tools, also see that it struggles to find solution when some number of such constraints (quite simple really) is introduced in the problem. I was not able to resolve it and looking forward to any comment.

[GuyBenhaim]

I hope this is just a syntax issue

[Mizux]

Solver add node one by one so let's say Solver add node A -> your constraint is not satisfied -> failed.

[GuyBenhaim]

I didn't understand. Should what I suggested work?
Phrasing differently: if one of the Nodes is not Active I'd like to force Solver to drop the other Node.

[GuyBenhaim]

Understood, since both Nodes are initially inactive, Solver will never visit/activate just one Node and force both the remain inactive ...
So we need a condition that takes effect only after one Node becomes Active, and then either makes the other Node Activate or makes them both Inactive. Making both Active is better, and of course, avoids 2xPenalty.

Maybe just use AddPickAndDrop without the same vehicle constraint?

[GuyBenhaim]

Doable?

[jmarca]

Can’t you just use a disjunction with cardinality of 2? Something like AddDisjunction([A,B],10000,2)

The docs say “exactly max_cardinality of the indices are active” so that should do the trick—force both active or pay a penalty

[GuyBenhaim]

Thx
Actually, I was looking for a 'hard' constraint. I will consider if cardinality can be a substitute.

[selting]

Hey @GuyBenhaim, I am currently having the same issue with optional visits for (pickup and delivery) pairs of nodes. I was wondering whether you found a solution for this problem and if so if would you mind sharing it?
I have tried the inital approach with an equality constraint on the ActiveVars() of the pair and thanks to you this discussion I understand why it will not find a solution.
Currently I have implemented the AddDisjunction method as decribed by @jmarca but although it will always produce a solution, in some instances only one part of a pickup and delivery pair is dropped but not the other.
It is surprising to me that these can be a solution since the hard equality constraint of equal vehicles
routing.solver().Add(routing.VehicleVar(pickup_index) == routing.VehicleVar(delivery_index))
is clearly ignored.

Any help is highly appreciated!

[GuyBenhaim]

Hello,
Sorry, I do not recall finding a perfect way for this. However, I did not try @jmarca's suggestion at the time. If I get some time, I will look again ...

[selting]

I found a solution that works for me. Obviously, I made a mistake in adding the constraints.

From my understanding, ["same vehicle" constraints + singleton disjunctions] should do the trick.
Nevertheless, this is probably not the hard constraint you were searching for. Also, I am yet to fully understand the AddDisjunction with max_cardinality = 2.

As far I can see atm, I found a working solution for my problem! So no need for you to search through your old code :) Appreciate your response to an outdated post!

[dimboukosis]

Hey @selting could you be more specific about the working solution you found?
I have the same problem as @GuyBenhaim for a roadside assistance problem.
If node A is active then node B must be routed together and visited after node A.
In what way did you solve this problem?
Thank you

[GuyBenhaim]

But NOT necessarily by the same vehicle .... (which P&D forces)

[selting]

It's been a minute since I had this problem. So, I'm not sure if I fully understand your problem atm. But here is a snippet I grabbed from my code

# PICKUP AND DELIVERY
routing.AddPickupAndDelivery(pickup_index, delivery_index)
solver.Add(routing.VehicleVar(pickup_index) == routing.VehicleVar(delivery_index))
solver.Add(total_time_dimension.CumulVar(pickup_index) <= total_time_dimension.CumulVar(delivery_index))

# OPTIONAL VISIT
disjunction_indexes.append(routing.AddDisjunction([pickup_index], penalty))
disjunction_indexes.append(routing.AddDisjunction([delivery_index], penalty))

I apply this by looping over all Pickup & Delivery pairs. In my particular case, the disjunctions were only applied for the last pair.