Negative values in transitCallback / Dimensions (Routing Package) possible?

[rbuergy]

Hi,

I try to use Google-OR Tools to solve a subproblem within a decomposition method. The subproblem is a variant of a so-called elementary shortest path problem with resource constraints. Unfortunately, I face various problems:

• Is it possible to specify a negative length from a node to another node? I think this leads to errors. However, no error message appears. Test: Change all distances to -1 in the vrp example (in transitCallbackIndex set return value to -1)
• In my problem, visiting a node is optional. You get a bonus or penalty when visiting a node. Is it possible to specify negative "penalties" (=bonus) in the routing.addDisjunction method? Test: When giving a "penalty" of -1 for each node in the vrp with penalties example, no solution is found anymore.

I also tried to use Dimensions with negative transit lengths, unfortunately without success.

By the way, is it possible to tell the routing solver to stop the search if some given objective value is attained?

I do not have a lot of experience with the Google OR-Tools. Please, apologize for taking your time.

Thanks for your hints!
Best regards,
Reinhard

[Mizux]

1. I would say negative arc should be supported since there is a "positive" version of the Transit callback:
   

   or-tools/ortools/constraint_solver/routing.h

   Lines 403 to 410 in fa84bc0

   	int RegisterUnaryTransitVector(std::vector<int64> values);
   	int RegisterUnaryTransitCallback(TransitCallback1 callback);
   	int RegisterPositiveUnaryTransitCallback(TransitCallback1 callback);
   	int RegisterTransitMatrix(
   	std::vector<std::vector<int64> /*needed_for_swig*/> values);
   	int RegisterTransitCallback(TransitCallback2 callback);
   	int RegisterPositiveTransitCallback(TransitCallback2 callback);

   
   note: I've never used negative arc

2. Using negative penalty seems to just force the max cardinality, i.e. not what you would like to do.
   

   or-tools/ortools/constraint_solver/routing.h

   Lines 622 to 626 in fa84bc0

   	/// 'penalty' must be positive to make the disjunction optional; a negative
   	/// penalty will force 'max_cardinality' indices of the disjunction to be
   	/// performed, and therefore p == 0.
   	/// Note: passing a vector with a single index will model an optional index
   	/// with a penalty cost if it is not visited.

   
   BTW you could offset all your penalties to have 0 or positive values ?

3. Currently only time limit or number of solutions limit is available through the API:
   

   or-tools/ortools/constraint_solver/routing_parameters.proto

   Lines 437 to 445 in fa84bc0

   	// -- Search limits --
   	// Limit to the number of solutions generated during the search. 0 means
   	// "unspecified".
   	int64 solution_limit = 8;
   	// Limit to the time spent in the search.
   	google.protobuf.Duration time_limit = 9;
   	// Limit to the time spent in the completion search for each local search
   	// neighbor.
   	google.protobuf.Duration lns_time_limit = 10;

   
   https://developers.google.com/optimization/routing/routing_options#search-limits

[rbuergy]

Hi Mizux,

Thanks for your quick reply.

1. Right, if there is a "positive" transit callback, then negative values should be ok for the other callbacks. I made some tests with negative transit values, but they all failed. For example: add a "negative" number of visits counter, like this in Python:
   routing.AddConstantDimension(-1,1000, True, "countDim") Make Farkas proof available in MPSolverInterface #1000 = bigValue
   creates problems (no solution found), even without adding a constraint to this dimension. Setting fix_start_cumul_to_zero to False seems to change something. I do not understand this behavior. (By the way, I need to set the cumulative variable to 0 at start).

2. I do not understand the comment "force the max cardinality". Not a problem, drop penalties are only a workaround in my case. What I would like to do is to use negative values in the callback of the "SetArcCostEvaluatorOfAllVehicles" method. And this seems not to work.

Offsetting penalties: Unfortunately not possible. In other words, I try to solve a (version of a) minimum simple-path problem in a graph with negative-weight cycles, an NP-hard problem and not possible to "offset" so that negative-weight cycles disappear.

3. Ok.

Thanks a lot!
Reinhard

[glanch]

Dear Reinhard,
have you found a solution to your problems? I am also trying to solve an ESPPTW with negative edge costs, thus I am facing the same issues.

Best, glanch

[rbuergy]

Hi glanch,
I was unable to solve the problem when I encountered it in 2021. Unfortunately, I haven’t revisited it since then. Nonetheless, I’m curious to know if the ESPPTW can be solved using the OR-Tools-Routing framework.

Best, Reinhard