torressa / cspy

A collection of algorithms for the (Resource) Constrained Shortest Path problem in Python / C++ / C#
https://torressa.github.io/cspy/
MIT License
77 stars 24 forks source link

Relax strict monoticity assumption of input resources #106

Open torressa opened 1 year ago

torressa commented 1 year ago

Not sure if there is a need to have the assumption of strictly monotone resources for inputs or if just monotone suffices. In any case, a check should also be done in preprocessing to ensure we error first and to avoid producing stupid solutions.

This is a very simple change, however there a implications for dominance checks:

--- a/src/cc/ref_callback.cc
+++ b/src/cc/ref_callback.cc
@@ -32,8 +32,6 @@ std::vector<double> additiveBackwardREF(
   if (edge_resource_consumption[critical_res] > 0) {
     new_resources[critical_res] = cumulative_resource[critical_res] -
                                   edge_resource_consumption[critical_res];
-  } else {
-    new_resources[critical_res] = cumulative_resource[critical_res] - 1;
   }
   return new_resources;
 }

Offspring of #104