Make Arc Costs dependent on Cumulative Variable

[Luca Fiaschi]

Hi,

I would like to model the situation where the arc cost between two nodes i,j depends on the the value of a certain cumulative variable at node i and j according to an arbitrary function.

cost[i,j] = func(cumul[i], cumul[j]) 

Is there an interface already there in the routing library? 

Otherwise, can somebody point me to an example on how can I loop over the variables and add this term to the energy?

Thanks and best,

LF

[Vincent Furnon]

I guess the context is the routing library. You can do this by constraining the slack variable of a dimension.

Suppose cumul(d)[i] and cumul(d)[j] correspond to dimension d.

Suppose you have a dimension d' (d_prime), for which the transition callback always returns 0.

You can constrain slack(d_prime) == solver->MakeElement(function_callback, cumul(d)[i], cumul(d)[j]).

To take this into account in the objective you need to add d' to the cost function with:

d_prime->SetSpanCostCoefficientForAllVehicles(1);

Note: performance of such a model might not be great (aka slow to solve). You can make it better by returning the lower bound of all f(cumul(d)[i], cumul(d)[j]) in the transit callback of d' and removing this lower bound from the function callback when you create the Element expression.

Vincent

--
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.

[Luca Fiaschi]

Hi Vincent,

thanks for your prompt reply. Sounds like an interesting idea let me see if I understand it correctly. 

In SetSpanCostCoefficientForAllVehicles  the span cost is computed by considering 

span_cost = coefficient * (dimension end value - dimension start value).

What I would like to have in the objective  is a summation of my function evaluated over all pair of nodes in the arcs visited by the route.

If I understand you correctly, with your constraint you are proposing that the cumulative variable d_prime at its end value would be equal to that summation which I would like to add to the objective. What would be the value of d_prime at the the start node?

Also, regarding your note, why would this help speeding up the solver? and how should I retrieve the lower bound  of all f(cumul(d)[i], cumul(d)[j]) if this is not known prior to calling the function?

Best

LF

[Jayadev Chandran]

Could you solve this? I also ran into same problem. I need to assign arc cost for a vehicle based on the cumul var of other dimensions.