routing: heuristics allUnperformed not working if node has no possible vehicle

[rdl]

I have an unexplained behaviour for a not so expected case with the routing package.
I have a set of node with vehicle constraints. I can implement them easily by removing values from their vehicleVar:

routing.vehicleVar(tn.googleID).removeValue(VehicleID);

One of these nodes has actually no vehicle left when I'm done with removing vehicles.

This seems to prevent the heuristics AllUnperformed from delivering a result.
As I understand it, having no vehicle left makes the domain of the variable trigger a global fail at the first propagation.
However, I would rather have expected that the node can simply not be reached by any vehicle and set as not active.

Besides not putting such nodes in the problem, do you have any workaround to propose?

Thank you
--
Renaud

[Vincent Furnon]

If the node is not optional, then this will fail (indeed the vehicle variable will become empty). To make a node optional you need to call RoutingModel::AddDisjunction(node_vector, penalty) where node_vector contains the node you want to make optional and penalty is a positive integer representing the penalty for not performing the node.

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/groups/opt_out.
 
 

[rdl]

This is related to the allUnperformed heuristics. My nodes are all optional.
When I leave some vehicles accepted for the concerned nodes, the heuristics succeeds.

--
Renaud

[Vincent Furnon]

Then you probably have a constraint which forces the node to be performed. When a node is optional its vehicle variable contains the value -1 (escape value for the unperformed state) and the corresponding ActiveVar should contain 0 (both variables are linked). The AllUnperformed heuristic just sets the ActiveVar for every node to 0.

Vincent

[rdl]

I do not have such constraint.
However, I have time window constraint on these nodes.
Time window are represented by a dimension of the routing problem.

Maybe the constraint comes from there?

[Vincent Furnon]

On Mon, Feb 11, 2013 at 11:59 AM, rdl <rena...@gmail.com> wrote:

I do not have such constraint.
However, I have time window constraint on these nodes.
Time window are represented by a dimension of the routing problem.

Maybe the constraint comes from there?

Normally no. However what do you return in the time dimension callback when both nodes are the same ?

About

 "routing.vehicleVar(tn.googleID).removeValue(VehicleID);"

can you check that all vehicle variables have at least -1 in their domain after adding these constraints ?

[rdl]

On Wednesday, February 13, 2013 1:31:55 AM UTC+1, Vincent Furnon wrote:

On Mon, Feb 11, 2013 at 11:59 AM, rdl <rena...@gmail.com> wrote:

I do not have such constraint.
However, I have time window constraint on these nodes.
Time window are represented by a dimension of the routing problem.

Maybe the constraint comes from there?

Normally no. However what do you return in the time dimension callback when both nodes are the same ?

0

About

 "routing.vehicleVar(tn.googleID).removeValue(VehicleID);"

can you check that all vehicle variables have at least -1 in their domain after adding these constraints ?

yes, they do all have -1

[Vincent Furnon]

Ok, here's my suggestion to help you debug. Create an assignment containing all the "next" variables of your model. Then set the value of these variables in the assignment such that next[i] = i (use Assignment::SetValue(const IntVar* const v, int64 value)), This will build an assignment corresponding to what "AllUnperformed" should do.

Then check the feasibility of this assignment by calling Solver::CheckAssignmentAssignment* assignment). If the solver cannot build a solution, it will log the constraints which are not satisfied. Before calling CheckAssignment, don't forget to call RoutingModel::CloseModel() first.

[rdl]

I did not know that "next[i] = i" was the condition for unrouted, so I did the following:

for a set of nodes (mentioned as dn), I executed the following code:

logger.info("vehicles for node: " + dn.googleID + "[" + (routing.vehicleVar(dn.googleID).toString()) + "]");
logger.info("next for node: " + dn.googleID + ": [" + (routing.nextVar(dn.googleID)) + "]");
if(routing.nextVar(dn.googleID) == null){
  logger.info("this is a null reference");               
}

On the console I get the following:

vehicles for node: 263[Vehicles263(-1 0)]
next for node: 263: [Nexts263(0..274)]
vehicles for node: 267[Vehicles267(-1 3)]
next for node: 267: [null]
this is a null reference
vehicles for node: 262[Vehicles262(-1 3)]
next for node: 262: [Nexts262(0..274)]
vehicles for node: 272[Vehicles272(-1 6)]
next for node: 272: [null]
this is a null reference

I am surprised to notice that the next variable for some nodes is actually null.
Does it mean that all possible values have been excluded?

BTW, I use GoogleCP through the Java API, maybe there is an explanation from there?

I'll try your experiment, but I first want to understand this.

[rdl]

To give more info: the "next" of my last 8 nodes is null.
I also have 8 vehicles, and I initialize the package with the call:

routing=new RoutingModel(CurrentGoogleID, problem.getVehicles().size(), startLocs, endLocs);

[Vincent Furnon]

When you are accessing variables from the constraint model, the indices are different from the node indices. To go from node indices (the ones you used in startLocs and endLocs for instance) to variables indices you need to call NodeToIndex from RoutingModel. For instance to get the vehicle variable of node dn.googleID, you would call routing.vehicleVar(routing.NodeToIndex(dn.googleID)) (same for nextVar and cumulVar). This applies both when creating the model and when inspecting solutions. Note that routing.start(vehicle) and routing.end(vehicle) return the "variable" indices and that routing.isStart() and routing.isEnd() take "variable" indices too.

This might explain why you are getting null variables.

Vincent

[rdl]

OK, i though it was only to follow a route once a solution was found.

thank you, maybe my blocking comes simply from there.

[Nikolaj]

Hello,

Maybe

http://or-tools.googlecode.com/svn/trunk/documentation/user_manual/manual/tsp/model_behind_scene.html

might help?

Nikolaj

>>>> (routing.vehicleVar(dn.**googleID).toString()) + "]");

>>>> logger.info("next for node: " + dn.googleID + ": [" +
>>>> (routing.nextVar(dn.googleID)) + "]");

>>>> if(routing.nextVar(dn.**googleID) == null){

>>>> logger.info("this is a null reference");
>>>> }
>>>>
>>>> On the console I get the following:
>>>>
>>>> vehicles for node: 263[Vehicles263(-1 0)]
>>>> next for node: 263: [Nexts263(0..274)]
>>>> vehicles for node: 267[Vehicles267(-1 3)]
>>>> next for node: 267: [null]
>>>> this is a null reference
>>>> vehicles for node: 262[Vehicles262(-1 3)]
>>>> next for node: 262: [Nexts262(0..274)]
>>>> vehicles for node: 272[Vehicles272(-1 6)]
>>>> next for node: 272: [null]
>>>> this is a null reference
>>>>
>>>> I am surprised to notice that the next variable for some nodes is
>>>> actually null.
>>>> Does it mean that all possible values have been excluded?
>>>>
>>>> BTW, I use GoogleCP through the Java API, maybe there is an explanation
>>>> from there?
>>>>
>>>> I'll try your experiment, but I first want to understand this.
>>>>
>>>>
>>>> On Monday, February 18, 2013 11:50:37 PM UTC+1, Vincent Furnon wrote:
>>>>>
>>>>> Ok, here's my suggestion to help you debug. Create an assignment
>>>>> containing all the "next" variables of your model. Then set the value of
>>>>> these variables in the assignment such that next[i] = i (use
>>>>> Assignment::SetValue(const IntVar* const v, int64 value)), This will build
>>>>> an assignment corresponding to what "AllUnperformed" should do.

>>>>> Then check the feasibility of this assignment by calling Solver::**CheckAssignmentAssignment*

>>>>> assignment). If the solver cannot build a solution, it will log the
>>>>> constraints which are not satisfied. Before calling CheckAssignment, don't
>>>>> forget to call RoutingModel::CloseModel() first.
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> On Wed, Feb 13, 2013 at 4:48 AM, rdl <rena...@gmail.com> wrote:
>>>>>
>>>>>>
>>>>>>
>>>>>> On Wednesday, February 13, 2013 1:31:55 AM UTC+1, Vincent Furnon wrote:
>>>>>>
>>>>>>>
>>>>>>> On Mon, Feb 11, 2013 at 11:59 AM, rdl <rena...@gmail.com> wrote:
>>>>>>>
>>>>>>>>
>>>>>>>> I do not have such constraint.
>>>>>>>> However, I have time window constraint on these nodes.
>>>>>>>> Time window are represented by a dimension of the routing problem.
>>>>>>>>
>>>>>>>> Maybe the constraint comes from there?
>>>>>>>
>>>>>>>
>>>>>>> Normally no. However what do you return in the time dimension
>>>>>>> callback when both nodes are the same ?
>>>>>>>
>>>>>>
>>>>>> 0
>>>>>>
>>>>>>
>>>>>>> About

>>>>>>> "routing.vehicleVar(tn.google****ID).removeValue(VehicleID);"

>>>>>>> can you check that all vehicle variables have at least -1 in their
>>>>>>> domain after adding these constraints ?
>>>>>>>
>>>>>>
>>>>>> yes, they do all have -1
>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> On Friday, February 8, 2013 3:39:11 PM UTC+1, Vincent Furnon wrote:
>>>>>>>>
>>>>>>>>> Then you probably have a constraint which forces the node to be
>>>>>>>>> performed. When a node is optional its vehicle variable contains the value
>>>>>>>>> -1 (escape value for the unperformed state) and the corresponding ActiveVar
>>>>>>>>> should contain 0 (both variables are linked). The AllUnperformed heuristic
>>>>>>>>> just sets the ActiveVar for every node to 0.
>>>>>>>>>
>>>>>>>>> Vincent
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> On Fri, Feb 8, 2013 at 3:30 PM, rdl <rena...@gmail.com> wrote:
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> This is related to the allUnperformed heuristics. My nodes are all
>>>>>>>>>> optional.
>>>>>>>>>> When I leave some vehicles accepted for the concerned nodes, the
>>>>>>>>>> heuristics succeeds.
>>>>>>>>>>
>>>>>>>>>> --
>>>>>>>>>> Renaud
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> On Friday, February 8, 2013 3:26:58 PM UTC+1, Vincent Furnon wrote:
>>>>>>>>>>
>>>>>>>>>>> If the node is not optional, then this will fail (indeed the
>>>>>>>>>>> vehicle variable will become empty). To make a node optional you need to

>>>>>>>>>>> call RoutingModel::AddDisjunction(**n******ode_vector, penalty)

>>>>>>>>>>> where node_vector contains the node you want to make optional and penalty
>>>>>>>>>>> is a positive integer representing the penalty for not performing the node.
>>>>>>>>>>>
>>>>>>>>>>> Vincent
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> On Fri, Feb 8, 2013 at 3:10 PM, rdl <rena...@gmail.com> wrote:
>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> I have an unexplained behaviour for a not so expected case with
>>>>>>>>>>>> the routing package.
>>>>>>>>>>>> I have a set of node with vehicle constraints. I can implement
>>>>>>>>>>>> them easily by removing values from their vehicleVar:
>>>>>>>>>>>>

>>>>>>>>>>>> routing.vehicleVar(tn.**googleID******).removeValue(**
>>>>>>>>>>>> VehicleID);

>>>>>>>>>>>>
>>>>>>>>>>>> One of these nodes has actually no vehicle left when I'm done
>>>>>>>>>>>> with removing vehicles.
>>>>>>>>>>>>
>>>>>>>>>>>> This seems to prevent the heuristics AllUnperformed from
>>>>>>>>>>>> delivering a result.
>>>>>>>>>>>> As I understand it, having no vehicle left makes the domain of
>>>>>>>>>>>> the variable trigger a global fail at the first propagation.
>>>>>>>>>>>> However, I would rather have expected that the node can simply
>>>>>>>>>>>> not be reached by any vehicle and set as not active.
>>>>>>>>>>>>
>>>>>>>>>>>> Besides not putting such nodes in the problem, do you have any
>>>>>>>>>>>> workaround to propose?
>>>>>>>>>>>>
>>>>>>>>>>>> Thank you
>>>>>>>>>>>> --
>>>>>>>>>>>> Renaud
>>>>>>>>>>>>
>>>>>>>>>>>> --
>>>>>>>>>>>> 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/**grou******
>>>>>>>>>>>> ps/opt_out <https://groups.google.com/groups/opt_out>.

>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> --
>>>>>>>>>> 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/**grou****
>>>>>>>>>> ps/opt_out <https://groups.google.com/groups/opt_out>.

>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> --
>>>>>>>> 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/**grou**ps/opt_out<https://groups.google.com/groups/opt_out>
>>>>>>>> .

>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>> --
>>>>>> 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/**groups/opt_out<https://groups.google.com/groups/opt_out>
>>>>>> .

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