Suboptimal node connections

[shrddr]

Current routing engine has multiple issues listed below, new one should ideally fix all of them. Problem is, precise solution (aka Steiner Forest) is impossible in polynomial time - SOTA is something like O(2.5^workercount). So need to come up with a good approximation (hand-crafted for this specific graph structure).

❌these two are both commonly taken

✔️however most of the time you only need one of them

[shrddr]

❌ glish-based worker going to lynch farm + heidel worker going to glish ruins = 10CP:

✔️ when order swapped = 9CP:

[shrddr]

❌ if Ehwaz hill worker is processed before Pinto farm worker:

✔️ expected

possible fix?: at the point when Pinto is activated, check if any of its forward-looking neighbors (in this case - Ehwaz hill) is already activated; if yes, deactivate Ehwaz hill and reroute all affected jobs

[shrddr]

❌ third party optimizer producing a 400 CP empire yields 404 CP when imported:

✔️ but collapses to intended 400 CP by placing a tactical Zero-cost:

[Thell]

These issues are resolved by ordering nodes prior to import using re-weighted shortest paths. Since its implementation I have run into any mis-reported/non-optimal routing issues on imports of test instances.

This is how it is currently being ordered: https://github.com/Thell/milp-flow/blob/119d156e16849413eb7c5822fd73bdce7348700b/generate_workerman_json.py#L107

[shrddr]

the issue is about interactive site operation, when you hire and assign workers by hand in "wrong order"

[shrddr]

linked function refers to some kind of "solution" (the one that takes 2 hours to compute?) - there's no such thing in interactive workerman session

[Thell]

the issue is about interactive site operation, when you hire and assign workers by hand in "wrong order"

Understood and no, the ordering portion I linked isn't a part of the optimization at all and should only take milliseconds. Doing the full processing on a 100 node network it takes ~100ms using my non-optimized ordering code but you wouldn't need to do the whole thing, just whichever components are nearest. I don't know anything about how that kind of time would 'feel' like during user interaction.

Actually, I think you are actually already doing most of it. I used bellman ford but dijkstra would work just fine (actually better since it performs better on sparse graphs).

solution_distances is just the initial all_pairs distances between plants and their assigned towns from the solution which is the same as the original graph's all_pairs distances but whittled down to only those plants in the solution. So for you it would grow by 1 plant with each addition by the user, or be processed in full during import and then your normal dijkstra routine would/could be run on each (although I bet there is overlap in what you are doing and what the ordering is doing).