Time-out option

[jcoupey]

The -x flag defining the exploration level is a way to set a trade-off between computing time and solution quality. But in some situations (think huge instances) this parameter can be hard to tune. Also no matter the size it's sometimes interesting to reach out to a time-constrained solution ("give me the best solution you can get in X seconds").

We could add a -l LIMIT flag to pass in input a number of seconds the optimization run is allowed to span.

A few thoughts:

1. I think it's clearer if the value passed describes the overall computing limit, thus including parsing the input and retrieving the matrix from the routing engine (time after solving used for routing request and solution formatting is negligible here).
2. The point is to be able to stop the local search if it's taking too long based on the LIMIT value, but I don't think it makes sense at all to stop the heuristic process of getting initial routes. This means that actual computing time may be higher than LIMIT if the heuristic process has not completed before. My guess is that in most situations this would really only happen if the LIMIT is set to an unrealistically low value.
3. We can probably use seconds as unit for this parameter as I don't really see the point in using a higher precision.

[jcoupey]

The simplest way to get on with this is to add a stopping condition in LocalSearch::run, or even LocalSearch::run_ls_step.

Worth noticing that introducing such a parameter may change the resulting solution based on -t. For now, changing the -t value only impacts the way the (full) searches are distributed among threads. Now if a thread is responsible for several searches and the first is interrupted, then what will happen is that we'll only perform the heuristic phase for subsequent searches (see 2. above).

[jcoupey]

Worth noticing that introducing such a parameter may change the resulting solution based on -t.

Also of course hardware and system load while computing will impact how far we reach out in a given amount of time.

[jcoupey]

Now if a thread is responsible for several searches and the first is interrupted, then what will happen is that we'll only perform the heuristic phase for subsequent searches

Actually based on the number of searches per thread and timeout, it's possible to decide how much time we want to allocate to each search. The result is still highly dependent on system load/concurrency handling but this way all concurrent searches are equal in term of available time. This is much better than having a few long-running searches eating up all the time and the remaining ones stopped very early due to the timeout.

[nova26]

Hi Julien,
I think we will get the best result from the user perspective,
If we will include the overall computing time, i.e from the start of the process.
But, without stopping the heuristic process, or stop before.
In other words, the first point the running time will be check is after the heuristic process.

[jcoupey]

the first point the running time will be check is after the heuristic process.

This matches the way I did it in #595:

• Input::solve has a new (optional) timeout parameter
• it's responsible for subtracting loading time to the overall timeout and pass the remaining value on to vrp::solve
• then in cvrp::solve / vrptw::solve, each thread is in charge of chopping the available time based on the number of searches
• heuristic phase is always applied (duration not accounted in timeout)
• the LocalSearch class is responsible for stopping based on (optional) provided search time

From the tests I've performed, this works as expected with a total running time really close to the -l value, in part because heuristic computing times is negligible in the overall computing time.

[jcoupey]

This should be in a working state now in #595, happy to have any feedback!