Troubleshooting RoutingModel::ReadAssignmentFromRoutes ("warm-start")

[sascha...@gmail.com]

I have a large-scale (5000-6000 nodes; 400 vehicles) CVRPTW where the best construction-heuristic (parallel-cheapest insertion) struggles and needs ~ 6h of time to find any solution.

I know, that this is probably ~5 times too big for the usual use-cases of the solver.

One core characteristic of my instance is, that there is a discontinuous set of availability time-windows for each node (imagine a shift for each day of the week). There are no disjunctions / optional nodes!

Having observed that and knowing a bit about the structure of the problem, i implemented a construction-heuristic which is basically the same as parallel-cheapest insertion, but faster (and less general): a parallel insertion-heuristic (with constant-time insertion-checks; as we need to check ~6000^3 insertions).

Now i'm able to obtain a solution within ~5 minutes and want to "warm-start" the solver:

    A: const operations_research::Assignment* initial_solution = model->ReadAssignmentFromRoutes(initial_routes, true);
    B: VLOG(1) << absl::StrFormat("did solver accept warm-start? %d", initial_solution != nullptr);

Later:

    if(initial_solution == nullptr)
    assignment = model->SolveWithParameters(search_params);
    else
    assignment = model->SolveFromAssignmentWithParameters(initial_solution, search_params);

I also have a solution-callback in place:

    C: model->AddAtSolutionCallback(std::bind(&SolutionCallback::Run, &solution_callback));

Now things get strange as running this leads to:

- 1) 5 min own heuristic
- 2) ~6 min of or-tools doing stuff in ReadAssignmentFromRoutes (A)
- 3) Solution-callback (C) getting called indicating my passed solution -> correct vehicle-cardinality (~6 min after ReadAssignmentFromRoutes)
- 4) ??? additional work of the solver -> no further progress for > 8 hours ??? (within A)
- 5) NEVER REACHED -> VLOG(1) << absl::StrFormat("did solver accept warm-start? %d", initial_solution != nullptr);

B | 5)is NEVER REACHED (within 8 hours > which is more time than the in-built construction-heur would need)!

As logging isn't helpful, i tried to get an idea where i'm at:

- Debugger stacktrace tells me where are still in DoRestoreAssignment -> NextSolution() -> but why? We found a solution or else the callback should not be called? I first thought it's about instantiating secondary/free/non-signleton-domain variables, but i do think this has to be done before the callback-call.
- Profiling tells me the solver is still happily propagating costly stuff like: CumulRange, DelayedPathCumul, ...

I'm wondering what's happening here? I'm interested in quick-acceptance of that solution followed by some improvement-phase.

Scaling down leads to more confusion as:

- 100 nodes quickly show the A -> B transition
- 250 nodes struggle exactly as above despite being a small-scale problem (doing "something" for 15 minutes) not reaching B

I don't think that's whats happening, but it basically feels like the solver is doing a full DFS/enumeration to optimize (linear-scan) all free variables (shift slacks)". This kind of workflow is the only thing where i would understand the observations, but i don't think this is what should happen.

I don't see what i might have done wrong (and i'm also running memory-sanitized (ASAN) experiments to be pretty sure i don't have any strange undefined-behaviour "jumps").

Less relevant i guess, but this is: or-tools v9.6 (running on Ubuntu through WSL2).

Greetings,
Sascha

[sascha...@gmail.com]

Are there no ideas about what's happening or any tips on how to analyze this?

I guess the core question is: 

Should warm-starts (with lost information as we only post linear-orderings) work in the routing-solver even with large-scale instances (~5000-6000 nodes) or are there conceptional scalability issues (e.g. secondary variables; missing earl-stopping, ...)?

Thanks,

Sascha

[Nano Byte]

+1 on your questions.

cross post: https://groups.google.com/g/or-tools-discuss/c/GGqFJkjRQYU