Constraints on Slack Variables

[Josh Cogan]

Hi Everyone,

I am working on a routing problem in which I would like to allow the Slack Variable (or service time at each node) to not be fixed a priori.  Is this possible?  Looking at cvrptw.cc and pdptw.cc, it appears that Slack(index) must be known *before* the call to RoutingModel::Solve().  Said another way, the NodeEvaluator2 that is passed to AddDimension, must return a hard value (ie an int64), not an IntVar*.

An ideal solution for my problem would for APrioriKnownMaximum(i) > Slack(i) > APrioriKnownMinimum(i).

Thanks so much.

Josh

[Ondrej Sykora]

Hi Josh,

when you create a dimension with routing.AddDimension(callback, max_slack, capacity, start_is_zero, name), you it sets up the slack variable so that the slack is in the range (0, max_slack). After adding the dimension, you can also get the slack variable for any node (index) via routing.SlackVar(index) and add more constraints to it (or e.g. call routing.SlackVar(i)->SetRange(APrioriKnownMinimum(i), APrioriKnownMaximum(i)) to set per-node slack ranges).

Looking at cvrptw.cc, there are two dimensions - vehicle capacity with zero slack (so the value of the dimension is always exactly the used capacity), and time where the slack on any node can be any value in the range (0, kHorizon).

Please let me know if you have any other questions

Ondrej

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Josh Cogan]

Hi Ondrej,

In cvrtpw.cc however, when both dimensions are added they already have an implementation to return "Service Plus Transition", which I take to mean SlackVar(i) + Transit(i).  Notice that implementation returns  a cost, not an IntVar*.  But I have no way of knowing in the problem statement how much slack I want at each node.  

I think my problem is like "I have a traveling Jehovah's witness who wants to spend as much time as possible at each persons door.  He won't visit a house if he can't spend 2 minutes at each house, and won't spend more than 4 hours there.  He has a weighting function that rewards him for visitng more houses, and for spending more time at each. How would you implement the NodeEvaluator2, such that the service time (or slackvar) could be different for each house, and not set in the problem statement?

Thanks so much

Josh

[Josh Cogan]

Hi Ondrej,

Nevermind, I understand now.  My NodeEvaluator simply returns the transit time, and then I place additional constraints on the Slack/Cumul vars later.  Thank you for your advice.

While the solver addresses all my constraints, I'm still unable to ask the Assignment what the value taken by the SlackVar is, e.g.

//this works

solution->Value(routing.CumulVar(node, "time"));

//but this does not

solution->Value(routing.SlackVar(node, "time"));

I can work around this, but I figure I've missed a simple flags.  Any thoughts?

Josh

--
You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/Ti-zDA0ipqM/unsubscribe.
To unsubscribe from this group and all its topics, send an email to or-tools-discu...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
:wq

[Vincent Furnon]

You can call RoutingModel::AddToAssignment() for each slack variable before calling Solve() or closing the model. This will give you access to slack variable values after the search (only cumul variables are added by default).

Vincent

[Josh Cogan]

Great, thanks Vincent + Ondrej.  My program now excellent reflects all my constraints except one.  I don't wait to arrive at a node before I begin to service it.  Consider this table of CumulVar, SlackVar and TransitVar

Cumul Slack Transit DistanceToNext

0 0 3 3
108 2 4 2
112 2 4 2
156 2 4 2
160 2 5 3
165 6 8 2
173 2 8 6
181 2 6 4

I notice that Cumul[next[ii]] >= Cumul[ii] + Transit[ii].  Can I change this >= into a ==?  Also I would have expected the TransitVar[ii] = DistanceToNext, but it doesn't.  TransitVar reports SlackVar[ii] + DistanceToNext.  Any thoughts?

Josh

[Vincent Furnon]

Actually Cumul[next[ii]] == Cumul[ii] + Transit[ii] with TransitVar[ii] = DistanceToNext + SlackVar[ii]. To avoid waiting just constrain the upper bound of the slack var to be equal to the lower bound (I guess you only constrained the lower bound).

Vincent

[Josh Cogan]

Yes, you are correct, I only constrained the lower bound.  Unfortunately I think this brings me full circle back to my original problem: I want to spend as much time as possible servicing a node, and I dont' know how much that is before routing.

I think I'm understanding that this isn't possible, but please respond if I'm wrong.  I'll open a new thread so this one can be treated as solved and closed (since it is!)