Simple TSP with precedence constraints

[Void Dev]

Hello,

I've recently started with or-tools and wanted to apply precedence constraint for simple tsp problem - I wanted to specify some nodes to be visited at a certain step.

For example, I have 20 nodes and I want node 5 to be visited at 4th step, node 17 at 10th step, etc. Without specifing fixed nodes, the solver returns with good solution.

I figured out that I can "fix" nodes if I add disjunctions with penalty costs. That's the first thing what I don't understand - why? Without it solver doesn't return with any result.

With disjunction and penalties I can fix certain nodes, but in some cases I cannot fix any nodes, the solver drops them - even if I define maximum available penalty cost while the route costs are low (some hundreds).

Based on the guidelines, posts, I expected to be able to fix any nodes without disjunctions and have a less optimal result at the end. 

Hope you see, what is my problem. Could you please guide me - what did I miss?

Thanks,

Zoltan

[Mizux Seiha]

How did you model your precedence constraint ?

Maybe the solver find your constraint infeasible unless it can drop the node (thus the disjunction)...

[Void Dev]

Thank you for your answer! Here's the relevant piece of my code

            Distance cost_callback = new Distance(manager, costMatrix);
            int costCallbackIndex = routing.RegisterTransitCallback(cost_callback.Call);
            routing.SetArcCostEvaluatorOfAllVehicles(costCallbackIndex);

            // set up counter
            routing.AddConstantDimension(
                                            1,
                                            outputData.Count + 1,      //maximum capacity of vehicle
                                            false,                  //start cumul to zero
                                            "Counter");            //dimension name
            RoutingDimension countDimension = routing.GetMutableDimension("Counter");
           
            // set up orders
            for (int order = 0; order != outputData.Count; order++)
            {
                long ordidx = manager.NodeToIndex(order);
                long[] orders = { ordidx };
                routing.AddDisjunction(orders, 999999999999999999);

                if (outputData[order].FixedPosition != default)
                {
                    countDimension.CumulVar(ordidx).SetValue(outputData[order].FixedPosition);
                }
                else
                {
                    countDimension.CumulVar(ordidx).SetRange(0, outputData.Count + 1);
                }

            }

outputData contains list of nodes, together with the desired "fixed" positions, costMatrix contains the distance of nodes - the longest distance between two nodes is 55.

If certain node has a fixed position in than this is assigned to it as constraint, otherwise value can be assigned from the whole range of positions.

Perhaps, could it be problem that when no fixed position is assigned to a node, then from the whole range of positions any can be assigned and the solver assignes such position which is also assigned to other node as fixed one? This way, two nodes would be assigned to the same position and it's impossible as one vehicle cannot be at two nodes in the same time.

Hope, you see what I mean! Thank you in advance for any piece of advices!

Zoltan

[Mizux Seiha]

1) why using  `false,                  //start cumul to zero` when creating the counter dimension ? I would expect it to force start at zero.

2) if node is dropped I guess the CumulVar will be set to 0
So I would use:
```cpp

if (outputData[order].FixedPosition != default) {

-  countDimension.CumulVar(ordidx).SetValue(outputData[order].FixedPosition);
+countDimension.CumulVar(ordidx).SetValues([outputData[order].FixedPosition,0]); // 0 if it is dropped

}

```

3) else is useless since by default all cumulVar are setup to the dimension full range aka [0, max capacity] aka [0, outputData.Count + 1]

Otherwise you can try to use a constraint instead only enable if node is active
``'py

index = manager.NodeToIndex(node)
active = routing.ActiveVar(index)

routing.solver().Add(
        active * count_dimension.CumulVar(index) == active * outputData[order].FixedPosition))
```

[Void Dev]

Thank you for the help, I appreciate it very much!

Actually after my previous answer I changed the code like below and it is working as expected.

            for (int order = 0; order != outputData.Count; order++)
            {
                long ordidx = manager.NodeToIndex(order);

                if (outputData[order].FixedPosition != default)
                {
                    countDimension.CumulVar(ordidx).SetValue(outputData[order].FixedPosition);
                }
                else
                {

                    countDimension.CumulVar(ordidx).SetValues(unassigned);
                }

            }

In the else part, unassigned is an array which contains nodes without fixed position.

From this it seems to me that solver doesn't take out 'automatically' the fixed positions from the whole range of cumulVar and sometimes trys to assign a node to a certain position even if it that position is a "fixed" one for an other node.

Thank you again for your support!