Time limits for algorithms

[Rhyd Lewis]

Hi, 

I am hoping to add some new algorithms and heuristics to NetworkX in the future. These will be mostly concerned with my published work on cycles and graph colouring.

https://link.springer.com/content/pdf/10.1007/s10878-023-01091-w.pdf

https://link.springer.com/book/10.1007/978-3-030-81054-2

Some of these heuristics run according to a user-specified time limit; however, I have not seen any other algorithms in NetworkX that use time limits as a paramter. Is this allowed, or is there a specific policy against it?

Thanks for the advice

Rhyd Lewis

[Dan Schult]

NetworkX doesn't have explicit time limits. But we have many features/functions where time limits can be implemented easily by the user. Our strategy is to use generators that yield partial results. By their nature the generators pause computation until the calling function requests the next output. This makes it easy for the user to e.g. check the time taken so far and choose to stop or continue.  This doesn't work for all computations/algorithms. But it is a very powerful technique. The algorithm doesn't get interrupted in a partial state, Python handles the communication, the user gets complete control over whether to ask for more or stop. It does require that the user make use of this possibility. But it seems pretty powerful.

As you think about how to implement the algorithms you've developed in Python, you should consider this approach as one possibility. We do not rule out user specified time limit parameters. But they are tricky to implement well. It is often easier to implement a work-limit (e.g. `cutoff` in BFS or DFS or shortest_path) than a time-limit. And using generators is the easiest way to make that work.

Best,

Dan

[Rhyd Lewis]

Hi Dan,

Thanks for your reply. I understand your point about the desirability of using generators. The NetworkX function nx.simple_cycles(G) is a good example of when this is very useful as it allows the user to iterate through all cycles in a simple graph.

When I asked my question, I was thinking more about heuristic optimisation algorithms where we are interested in finding the best solution among many different options. In these cases, a generator seems to be less useful because the user will only really be interested in the best solution that the algorithm found (and not the inferior solutions that it looked at along the way). Allowing the user to state some sort of computational limit on a heuristic optimisation algorithm up front also allows values for any internal control parameters to be determined by the algorithm.

As a guide, I've been looking at the simulated annealing algorithm for the travelling salesman problem in the NetworkX library. This is more like the sort of thing I have in mind.

https://networkx.org/documentation/stable/_modules/networkx/algorithms/approximation/traveling_salesman.html#simulated_annealing_tsp

In this example, lengths of runs are specified using several user-defined parameters (things like temp, max_iterations, N_inner and alpha). While this only gives the user indirect control over how long the algorithm will run for, it does mean that runs with the same input always produce the same output.

Unless advised otherwise, I think, then, that I will use the above simulated annealing example a guide in my implementations. I will run the optimisation process for a fixed number of iterations (defined by the user) and will make a note of the computation complexity of each iteration in the documentation.

Thanks

Rhyd

[David Menéndez Hurtado]

On Tue, 16 Jan 2024, 14:38 Rhyd Lewis, <rhydia...@gmail.com> wrote:

Hi Dan,

Thanks for your reply. I understand your point about the desirability of using generators. The NetworkX function nx.simple_cycles(G) is a good example of when this is very useful as it allows the user to iterate through all cycles in a simple graph.

When I asked my question, I was thinking more about heuristic optimisation algorithms where we are interested in finding the best solution among many different options. In these cases, a generator seems to be less useful because the user will only really be interested in the best solution that the algorithm found (and not the inferior solutions that it looked at along the way). Allowing the user to state some sort of computational limit on a heuristic optimisation algorithm up front also allows values for any internal control parameters to be determined by the algorithm.

As a guide, I've been looking at the simulated annealing algorithm for the travelling salesman problem in the NetworkX library. This is more like the sort of thing I have in mind.

https://networkx.org/documentation/stable/_modules/networkx/algorithms/approximation/traveling_salesman.html#simulated_annealing_tsp

In this example, lengths of runs are specified using several user-defined parameters (things like temp, max_iterations, N_inner and alpha). While this only gives the user indirect control over how long the algorithm will run for, it does mean that runs with the same input always produce the same output.

Another option is to run in the background, keeping the best solution so far in a structure exposed to the user. At any point, the user can inspect the solution, decide it is good enough and stop it.

It can also be used to provide feedback on the process.

/David