[dotnet::routing] CSharp Context based Wrappers review #2249
Replies: 22 comments 25 replies
-
|
See edits in the OP text. Adding links to related source... |
Beta Was this translation helpful? Give feedback.
-
|
I moved it to a discussion topic, but you should try to cross post in the mailing list (with a ref link here) to reach more people |
Beta Was this translation helpful? Give feedback.
-
|
@Mizux Appreciate the feedback, I will try that. Perhaps I have not been as focused as I could be in the mailing list format. My aim is twofold, first to exercise the wrapper architecture. I think I have covered much of the bases there, with other aspects, facets, etc, that can be added later as needed. Second, to demonstrate a couple of potential use cases, illustate usage, etc. Sort of hitting that one, but I think it is missing the mark, for the aforementioned reasons, concerning which I could a bit of educated guidance. |
Beta Was this translation helpful? Give feedback.
-
|
@Mizux Can you or anyone on the ortools team offer any insights? After all, I'd consider that more authoritative than anyone else on the discussion forum, at any rate. So far that has been silence, no response. Hence connecting here with my repository, perhaps that will allow for more informed insight as to what it is I am trying to accomplish. Thanks... |
Beta Was this translation helpful? Give feedback.
-
|
@Mizux From general to specific dimension questions, hopefully the comments make it clearer what my test dimensions are trying to accomplish. Nothing is firmly written in stone where this is concerned, least of all the extent to which I can learn and adapt a better approach. |
Beta Was this translation helpful? Give feedback.
-
|
Changed the title. Yes, I did encounter an instance where I received a Title indicates opening the floor for review of the approach. I think it is sound, looking for a bit of feedback, advice, guidance, what could be improved, etc, etc. More of the Additionally, I am considering whether extension methods to expose these areas are not a better solution; i.e. to keep the Context clean as possible. But all that is TBD and on an as needed basis. |
Beta Was this translation helpful? Give feedback.
-
|
So... A bit of feedback on my part. So far so good, I started by adding the first of the Traveling Salesman Problems as a unit test around the wrapper scaffold, and after a bit of effort around the matrix, dimension, etc, the response comes out identical to that of the illustration. So that's a good bit of confirmation so far, as far as I'm concerned. Will work through the other aspects as well, which, I expect, may also drive further wrapper discoveries, gaps in exposure, etc, along these lines. Output literally, vis-a-vis the xUnit |
Beta Was this translation helpful? Give feedback.
-
|
@Mizux Trying to reconcile the circuit board example, so far I am unable to do so. The searchParams.FirstSolutionStrategy = FirstSolutionStrategyType.PathCheapestArc;And as far as I know I am calculating the distance correctly: private static double Squared(double x) => Math.Pow(x, 2d);
private static int Sqrt(double d) => (int)Math.Sqrt(d);
private static int?[,] CalculateEuclidianDistanceMatrix(int[,] coords)
{
// Calculate the distance matrix using Euclidean distance.
var length = coords.GetLength(0);
var matrixValues = new int?[length, length];
void OnCalculateDistance((int fromNode, int toNode) coord)
{
//// As compared with the original:
//distanceMatrix[fromNode, toNode] = (long)
// Math.Sqrt(
// Math.Pow(locations[toNode, 0] - locations[fromNode, 0], 2) +
// Math.Pow(locations[toNode, 1] - locations[fromNode, 1], 2));
matrixValues[coord.fromNode, coord.toNode] = Sqrt(
Squared(coords[coord.toNode, 0] - coords[coord.fromNode, 0])
+ Squared(coords[coord.toNode, 1] - coords[coord.fromNode, 1])
);
}
var dim = Enumerable.Range(0, length).ToArray();
// Zero the diagonal, which is handled by the matrix itself.
dim.AsCoordinates().Where(coord => coord.x != coord.y).ToList().ForEach(OnCalculateDistance);
return matrixValues;
}Will push what I have so maybe you could take a quick look at it, if you please. As background, as previously mentioned, the initial TSP solution does align with the illustrated example. So not quite sure what is different about this one that it is not repeatable. Or maybe the path itself does not matter quite as much as the Edit: Pushed. See links above. Concerning the core illustration bits, the bits are a bit dispersed throughout, from an architectural perspective. Hopefully that is not too difficult to follow. |
Beta Was this translation helpful? Give feedback.
-
|
@Mizux And here is the aligned output... It matches, to a point, then falls apart. Maybe it is the difference between |
Beta Was this translation helpful? Give feedback.
-
|
@Mizux Furthermore, when I configure with the void OnConfigureSearchParameters(object sender, RoutingSearchParametersEventArgs e)
{
var e_searchParams = e.SearchParameters;
e_searchParams.FirstSolutionStrategy = FirstSolutionStrategyType.PathCheapestArc;
e_searchParams.LocalSearchMetaheuristic = LocalSearchMetaheuristicType.GuidedLocalSearch;
e_searchParams.TimeLimit = new Duration { Seconds = 30L };
e_searchParams.LogSearch = true;
}I have stepped through all these in debug and verified, the search does run the time limit. Could any of this be platform specific? i.e. that is, I mean, you have how many CPUs? Cores? Hyper-threaded? Etc? Meaning, you arrive at solution I am running on an AMD Ryzen Threadripper 2950X 16-core CPU. Cheers. |
Beta Was this translation helpful? Give feedback.
-
|
Hi, |
Beta Was this translation helpful? Give feedback.
-
|
@Mizux Appreciate the response, good to know. Is there any way we can know that for sure? Is there an actual sample, etc, for instance? |
Beta Was this translation helpful? Give feedback.
-
|
I am using |
Beta Was this translation helpful? Give feedback.
-
|
@Mizux So... the poignant question for me is, is repeatability to be expected? Obviously, if underlying algorithms are at all shifting with the |
Beta Was this translation helpful? Give feedback.
-
|
See comments above. This is an issue, need to know the version(s) supporting the docs in order to make a sound assessment comparing notes with my scaffold and the underlying bits. On the plus side, I am more confident that the scaffold could actually work to meet my intended objectives in wrapping a convenience, disposable wrappers around the inner workings, boilerplate, and other grunt efforts. |
Beta Was this translation helpful? Give feedback.
-
|
Pushed past the above open questions to the initial VRP; so far so good, I can verify this given my scaffold and unit test scenarios. |
Beta Was this translation helpful? Give feedback.
-
|
@Mizux Should also clarify, there are a few discrepancies, I think, in the code, and the supported report, however, the core bits seem to align comparing notes between my scaffold, its unit tests, and the web site results. Yet, I will confess, this does not come as that much of a surprise in the default search parameters; if we went the path of a guided local search, I might expect different results, although potentially consistent in qualitative ways, i.e. a total distance that is less than, for example. |
Beta Was this translation helpful? Give feedback.
-
|
@Mizux Moving on to Pickup and delivery comprehension... Am I correct in saying the "event" of adding pickup and delivery should also add constraints? Is there ever a reason why NOT to add vehicle equality, and route distance constraints? Thank you... |
Beta Was this translation helpful? Give feedback.
-
|
From top of my head I don't see any reason, I would also say I don't understand why the or-tools/ortools/constraint_solver/routing.h Lines 688 to 703 in b77bd3a and you may also use this call AddPickupAndDelivery() each time you add a "same vehicle" constraint to the model...
|
Beta Was this translation helpful? Give feedback.
-
|
@Mizux Also, side note, what does this mean in terms of the disjunction version of the method? void RoutingModel.AddPickupAndDeliverySets(int pickupDisjunction, int deliveryDisjunction) { } |
Beta Was this translation helpful? Give feedback.
-
|
Seems a bit cleaner now based on re-reading the example: public virtual void AddPickupAndDelivery(int pickupNode, int deliveryNode, Dimension dim)
{
var (pickupIndex, deliveryIndex) = (
this.NodeToIndex(pickupNode)
, this.NodeToIndex(deliveryNode)
);
void OnAddPickupAndDelivery(RoutingModel model, Solver solver, RoutingDimension routingDim)
{
model.AddPickupAndDelivery(pickupIndex, deliveryIndex);
IEnumerable<Constraint> GetPickupAndDeliveryConstraints()
{
yield return model.VehicleVar(pickupIndex) == model.VehicleVar(deliveryIndex);
yield return routingDim.CumulVar(pickupIndex) <= routingDim.CumulVar(deliveryIndex);
}
GetPickupAndDeliveryConstraints().ToList().ForEach(solver.Add);
}
var dim_MutableDim = dim.MutableDimension;
OnAddPickupAndDelivery(this.Model, this.Solver, dim_MutableDim);
}Note that there is the |
Beta Was this translation helpful? Give feedback.
-
|
Question: where does |
Beta Was this translation helpful? Give feedback.
-
|
from this kind of missing line My guess, the line have been removed (why?) and the output has not been updated accordingly |
Beta Was this translation helpful? Give feedback.
-
|
Ah I see, thank you. Also, thanks for taking the time retrospectively. Much appreciated. |
Beta Was this translation helpful? Give feedback.
-
|
@Mizux Another example discrepancy, at least if I take the literal illustrated example results. Assuming that I've got the matrix aligned properly as well, but the stated assumption is also that it is the same as the vehicle matrix, so... the expected result is, indexed by the Yet the actual paths are: On the plus side, I visually inspected the results, and at least the pickup/delivery constraints are in agreement with the expected pairings: And double checking the overall var evaluatorIndex = this.RegisterTransitEvaluationCallback(this.OnEvaluateTransit);
this.SetArcCostEvaluators(evaluatorIndex);
this.AddDimension(evaluatorIndex, scope.VehicleCapacity);
// ^ 3000
this.MutableDimension.SetGlobalSpanCostCoefficient(this.Coefficient);
// ^ 100
this.AddPickupsAndDeliveries(scope.PickupDeliveries);So... I think the bottom line there may be to verify that the pairings are correct. Whether the actual route can be verified is not guaranteed. Again, it may also be a matter of verifying the |
Beta Was this translation helpful? Give feedback.
-
|
Which can also be verified: void OnVerifyPickupDelivery((int pickup, int delivery) node)
{
var (pickup, delivery) = node;
var actualPathMatches = scope.SolutionPaths
.Select(_ => (
path: _
, pickupIndex: _.IndexOf(pickup)
, deliveryIndex: _.IndexOf(delivery)
))
.Where(_ => _.pickupIndex >= 0 && _.deliveryIndex >= 0)
.Where(_ => _.pickupIndex < _.deliveryIndex).ToArray();
var actualPath = actualPathMatches.Select(_ => _.path).SingleOrDefault().AssertNotNull();
}
scope.PickupDeliveries.ToList().ForEach(OnVerifyPickupDelivery); |
Beta Was this translation helpful? Give feedback.
-
|
Backtracking a little bit... @Mizux In the Circuit Board example, runs as an extension of the TSP pattern, right. I did not see where the dimension is actually beening added to |
Beta Was this translation helpful? Give feedback.
-
|
Base CB case study example still failing for the difference in expected path: |
Beta Was this translation helpful? Give feedback.
-
|
I can also report, it seems like the guided local search is now "passing", but not without some "help". Configured as follows: void OnConfigureSearchParameters(object sender, RoutingSearchParametersEventArgs e)
{
var e_searchParams = e.SearchParameters;
e_searchParams.FirstSolutionStrategy = FirstSolutionStrategyType.PathCheapestArc;
e_searchParams.LocalSearchMetaheuristic = LocalSearchMetaheuristicType.GuidedLocalSearch;
e_searchParams.TimeLimit = 30L.AsDuration();
e_searchParams.LogSearch = true;
}Also, interestingly enough, started off with the web site indication of expected total distance, That failed, and was scope.ExpectedPaths = Range<int[]>(
Range(0, 3, 276, 4, 5, 6, 8, 7, 9, 10, 11, 14, 12, 13, 23, 22, 24, 21
, 25, 26, 27, 28, 125, 126, 127, 20, 19, 130, 129, 128, 153, 154, 152
, 155, 151, 150, 177, 176, 175, 180, 161, 160, 174, 159, 158, 157, 156
, 118, 119, 120, 121, 122, 123, 124, 29, 30, 31, 32, 33, 34, 35, 36
, 37, 38, 39, 40, 41, 42, 59, 60, 58, 43, 44, 45, 46, 47, 48, 49
, 50, 51, 52, 53, 54, 55, 56, 57, 67, 68, 66, 69, 70, 71, 72, 73
, 75, 74, 76, 77, 78, 80, 81, 88, 79, 92, 93, 94, 95, 96, 97, 98
, 99, 100, 101, 102, 91, 90, 89, 108, 111, 87, 82, 83, 86, 112, 115
, 85, 84, 64, 65, 63, 62, 61, 117, 116, 114, 113, 110, 109, 107, 103
, 104, 105, 106, 173, 172, 171, 170, 169, 168, 167, 166, 165, 164, 163
, 162, 187, 188, 189, 190, 191, 192, 185, 186, 184, 183, 182, 181, 179
, 178, 149, 148, 138, 137, 136, 266, 267, 135, 134, 268, 269, 133, 132
, 131, 18, 17, 16, 15, 270, 271, 272, 273, 274, 275, 259, 258, 260, 261
, 262, 263, 264, 265, 139, 140, 147, 146, 141, 142, 145, 144, 198, 197
, 196, 193, 194, 195, 200, 201, 199, 143, 202, 203, 204, 205, 206, 207
, 252, 253, 256, 257, 255, 254, 251, 208, 209, 210, 211, 212, 213, 214
, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 232
, 233, 234, 235, 236, 237, 230, 231, 228, 229, 250, 245, 238, 239, 240
, 241, 242, 243, 244, 246, 249, 248, 247, 277, 278, 2, 279, 1, 0).ToArray()
).ToList();So, not sure what's going on there. Clearly "different" from the web site in the total distance, but the expected path does agree. Strange. |
Beta Was this translation helpful? Give feedback.
-
|
Following through to the time window case studies, I cannot verify the indicated solution, but it is at least somewhat predictable. I think in the above report, the summary needs to be a bit different; or at least, the end state of the accumulators is more along the lines of the configured dimension However, doing a bit of math, if we just take the minimum time frame, this does not fall within the vehicle capacities... Maybe involving capacity plus slack? That is, capacity is @Mizux Have I got an accurate picture of this? |
Beta Was this translation helpful? Give feedback.
-
|
@Mizux FYI, re: the above concerns...
|
Beta Was this translation helpful? Give feedback.
-
|
@Mizux Trying to reconcile the resource constraint time window example... One of the assumptions is that it "builds on" the VRPTW example, right... However, straight out of the gate, the time windows disagree... So... how can that be the assumption? Shall I assume the windows illustrated by the CVRPTW example, then? |
Beta Was this translation helpful? Give feedback.
-
Absolutely, which is helpful to discover wrapper adapter coverage as well.
Also, absolutely. 👍 However, I am finding the results fail to align with my unit tests, hence much of my line of questioning here... Again, knowing the version of OR-tools that was employed to arrive at those results, might be a starting point making sense of that comprehension. |
Beta Was this translation helpful? Give feedback.
-
|
@lperron @Mizux Honestly, I have not introduced any of the constraints in the CVRPTW example, yet, and the results that I am getting already agree with the example. How can that be? I have not done the effort yet to adapt the additional API, because for me this question is front of mind and deserves being addressed. Right now I am seriously questioning the legitimacy, the credibility, of these examples. As far as which API are exposed, discovery for my wrapper adapters, serves its purpose, of course, but the data, the results, cannot say the same. |
Beta Was this translation helpful? Give feedback.
-
|
Reviewing my code versus the example, ... work in progress. Still I question considering my experiencing comparing notes thus far. Also, not to nit too badly here... for (var i = 0; i < data.VehicleNumber; i++)
{
// Add load duration at start of routes.
intervals[2 * i] = solver.MakeFixedDurationIntervalVar(timeDimension.CumulVar(routing.Start(i)), data.VehicleLoadTime, "depot_interval");
// ^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^ (?)
// Add unload duration at end of routes.
intervals[2 * i + 1] = solver.MakeFixedDurationIntervalVar(timeDimension.CumulVar(routing.End(i)), data.VehicleUnloadTime, "depot_interval");
// ^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^ (?)
}Should it be start/unload and end/load pairings? Just thinking in logistical terms there. When vehicles arrive, typically they unload what they have; before being able to receive any new load. How does that align with the model notion of start/end, for instance? |
Beta Was this translation helpful? Give feedback.
-
|
Let's assume that the wrapper introduces similar fixed duratoin interval pariings... Which has ownership of them? The containing protected internal virtual void AddFixedDurationIntervals(int vehicle, (long start, long end) interval, string name)
{
var this_MutableDim = this.MutableDimension;
IEnumerable<object> MakeFixedDurationIntervals(Solver solver)
{
IEnumerable<(long index, long interval)> GetVehicleIndexes(RoutingModel model)
{
yield return (model.Start(vehicle), interval.start);
yield return (model.End(vehicle), interval.end);
}
return GetVehicleIndexes(this.Context.Model).Select(_ =>
solver.MakeFixedDurationIntervalVar(this_MutableDim.CumulVar(_.index), _.interval, name)
);
}
// TODO: TBD: which we turn around and add to the list of children...
// TODO: TBD: do we need to dispose of disposable children?
MakeFixedDurationIntervals(this.Context.Solver).ToList().ForEach(this.Children.Add);
} |
Beta Was this translation helpful? Give feedback.
-
|
Okay, CVRPTW results do agree, insofar as they have been illustrated. More or less. The routes tend to agree. I am still confused concerning the route totals; not sure how to interpret that in the examples versus what is actually there in my unit tests. @Mizux @lperron Follow up question, however; the step which constrains cumulative depot usage does not make sense. If I interpret the usage summary as compared with the contributing vehicle start/end intervals, is it not possible for a single vehicle to contribute to the depot capacity for its protected internal virtual void AddDepotUsageConstraint(string intervalName, long capacity, string name)
{
// TODO: TBD: is this really the right constraint to be adding?
// TODO: TBD: what prohibits the same vehicle from contributing "twice" to capacity?
var intervals = this.Children.OfType<IntervalVar>().Where(_ => _.Name() == intervalName).ToArray();
var depotIntervalUsage = intervals.Select(_ => 1).ToArray();
void OnAddDepotUsageConstraint(RoutingModel model, Solver solver)
{
var constraint = solver.MakeCumulative(intervals, depotIntervalUsage, capacity, name);
solver.Add(constraint);
}
OnAddDepotUsageConstraint(this.Context.Model, this.Context.Solver);
} |
Beta Was this translation helpful? Give feedback.
-
|
@Mizux Appreciate the feedback concerning the charts.
I wondered about that, and whether SVG was a good fit for it, but moreover, considered for |
Beta Was this translation helpful? Give feedback.
-
|
@Mizux @lperron Following up today on the Penalties and Dropping visits example. I arranged my data, dimension bits, search parameters, etc, according to the example, and I cannot verify the results. Failing to align the result solution path. It does at least discover a solution, apparently, just not the one we are expecting, if we take the example data, results, etc, as gospel truth. Given past experience with the demands constraints in the previous examples, this is not altogether surprising at this point, sadly. Would be very, very helpful to have the Google.OrTools version indicated that we can more accurately compare results. Will have code committed that you can take a look. |
Beta Was this translation helpful? Give feedback.
-
|
@Mizux @lperron It's trying to solve, but it just does not solve in the expected solution, again, taking the example as gospel truth. |
Beta Was this translation helpful? Give feedback.
-
|
Walking through the code review, here are the highlights:
|
Beta Was this translation helpful? Give feedback.
-
|
@Mizux @lperron Concerning RoutingModel.ReadAssignmentFromRoutes, this is in terms of indexes? Or nodes? Assuming they are |
Beta Was this translation helpful? Give feedback.
-
|
@Mizux Did a bit of work establishing enum and other convenience bridges adapting the Google bits vis-a-vis the wrapper scaffold. Currently, I am 90% confident in some of the unit test results. Also confident in the scaffold. Less confident in other bits of the unit tests results; I suspect it is a package version, but, as I've said repeatedly, would be helpful to identify the My repository will be pushed shortly for your cross reference. Thank you. |
Beta Was this translation helpful? Give feedback.
-
|
@Mizux @lperron I am giving this a little space for response before deciding in what condition to publish the wrappers, but I do want to respond informed by a sensible response. Would you mind taking a look and providing some constructive feedback? Vis a vis:
Thank you. |
Beta Was this translation helpful? Give feedback.
-
|
@lperron @Mizux So... No response, safe to assume my assumptions are probably accurate vis-a-vis package dependency versions, etc. |
Beta Was this translation helpful? Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
Using the nuget v7.4 package,
dotnet,CSharp.I'll go ahead and post this so that perhaps I can get some informed feedback advising what adjustments I may need to make. When I have the repo committed I will post links to the modules in question.
Maybe it is my routing dimension, I have been unsuccessful configuring the dimension vehicle capacity, impose a disjunction, which I gather would prohibit scheduling certain nodes (?), and in fact it took invoking
SetAllowedVehiclesForIndexto get any sense of restricting scheduling of vehicles to certain nodes at all. When the solution isnull, where might we find a status, etc, in order to better diagnose what might be going on?I'll have my bits committed shortly to my repository, commit pending, maybe y'all could take a look and make some recommendations along these lines. My focus at first was to exercise an end to end usage use case, in order so that I could gain understanding what bits are necessary from my scaffold in order to facilitate routing. Eventually I will introduce more specific unit tests for the constituent components.
There are three prongs help to stand up the scaffold:
Context, embodies some utility methods,
RoutingIndexManagerthroughManagerContext,RoutingModelthroughRoutingContext, and, at a domain level,DomainContext<TNode, TDepot, TContext>; although I would argue that, in theory,RoutingContextis the bare minimum. Domain comprehension is good if there are additional bits necessary for theDimensionto make such decisions, but is unnecessary for the basics.Dimension, is the key to training the
RoutingModel. Initially I thought that there needed to be a binary/unary dimension, but I backed off of this assumption. Now there is simply domain and not domain.Finally, the RoutingProblemSolver also with domain versus not domain comprehension. Basically works with the context. Fundamentally, the main goal through all this is to provide sufficient scaffold in order handle much of the boilerplate details, dissecting routing problem solution assignment, for instance. That is quite repetitive, the package will add value where that sort of thing is concerned.
Visitor comprehension is also a thing, which affords subscribers an opportunity to transform the context according to their business needs. In some cases, for instance, nodes may be transformed, or vehicles, so on and so forth, before the context lands in the dimensions, is registered through dimensions, etc. Not important, I think for purposes of gaining preliminary comprehension, but might be good to know.
Beta Was this translation helpful? Give feedback.
All reactions