Speeding up brute force with n_jobs

Brute-force search evaluates every possible combination of candidate sites, which is thorough but gets slow fast as the number of candidates and the number of sites you want to choose (p) grows – see Solving larger problems for just how quickly that combinatorial cost climbs.

solve(..., n_jobs=...) lets you spread that evaluation across multiple CPU cores instead of a single process. This page shows how to use it, and – just as importantly – when it’s actually worth using.

We’ll reuse the same dataset as the no-geometry example – 28 candidate sites with no attached geometry, just demand and a travel time matrix.

Note

The data for this problem comes from github.com/health-data-science-OR/healthcare-logistics and is reused under the MIT licence.

Credit for the creation of this dataset goes to Dr Tom Monks.

from lokigi.site import SiteProblem

problem = SiteProblem()
problem.add_demand(
    "https://github.com/health-data-science-OR/healthcare-logistics/blob/master/optimisation/data/sh_demand.csv",
    demand_col="n_patients", location_id_col="sector")
problem.add_travel_matrix(
    "https://github.com/health-data-science-OR/healthcare-logistics/blob/master/optimisation/data/clinic_car_travel_time.csv",
    source_col="sector")

Using n_jobs

n_jobs=1 (the default, and what every other example on this site uses) evaluates every combination in the current process. Pass n_jobs=-1 to spread combinations across every available CPU core instead, or a positive integer (e.g. n_jobs=4) to request that many worker processes specifically.

solution = problem.solve(p=2, objectives="p_median", n_jobs=4, show_progress=False)
solution.show_solutions().head()

C:\lokigi\lokigi\site.py:743: UserWarning: No candidate site dataframe was given.
Sites names have been taken from the columns of your travel matrix: clinic_1, clinic_2, clinic_3, clinic_4, clinic_5, clinic_6, clinic_7, clinic_8, clinic_9, clinic_10, clinic_11, clinic_12, clinic_13, clinic_14, clinic_15, clinic_16, clinic_17, clinic_18, clinic_19, clinic_20, clinic_21, clinic_22, clinic_23, clinic_24, clinic_25, clinic_26, clinic_27, clinic_28.
If you wish to override this, run .add_sites() to add your site dataframe before running .solve() again.
You can use the .show_sites_format() to see the expected format beforehand.
  warn(

	solution_rank	site_names	site_indices	coverage_threshold	weighted_average	unweighted_average	90th_percentile	max	total_cost	proportion_within_coverage_threshold	...	gap_absolute_weighted	gap_relative_weighted	avg_lower_third_bins	avg_middle_third_bins	avg_upper_third_bins	inter_tertile_ratio	gap_absolute_description	gap_relative_description	inter_tertile_description	problem_df
0	1	[clinic_8, clinic_25]	[7, 24]	None	14.62	19.75	36.26	42.60	NaN	NaN	...	None	None	None	None	None	None	N/A (No equity data)	N/A (No equity data)	N/A (No equity data)	sector  clinic_8  clinic_25  min_cost sele...
1	2	[clinic_10, clinic_12]	[9, 11]	None	14.91	18.68	31.75	47.67	NaN	NaN	...	None	None	None	None	None	None	N/A (No equity data)	N/A (No equity data)	N/A (No equity data)	sector  clinic_10  clinic_12  min_cost sel...
2	3	[clinic_1, clinic_8]	[0, 7]	None	14.92	20.96	41.41	48.05	NaN	NaN	...	None	None	None	None	None	None	N/A (No equity data)	N/A (No equity data)	N/A (No equity data)	sector  clinic_1  clinic_8  min_cost selec...
3	4	[clinic_10, clinic_25]	[9, 24]	None	14.94	19.92	36.46	43.48	NaN	NaN	...	None	None	None	None	None	None	N/A (No equity data)	N/A (No equity data)	N/A (No equity data)	sector  clinic_10  clinic_25  min_cost sel...
4	5	[clinic_8, clinic_28]	[7, 27]	None	14.99	19.61	32.96	42.27	NaN	NaN	...	None	None	None	None	None	None	N/A (No equity data)	N/A (No equity data)	N/A (No equity data)	sector  clinic_8  clinic_28  min_cost sele...

5 rows × 26 columns

Same results, whichever way you run it

n_jobs=1 always produces byte-for-byte identical output to every other lokigi search strategy. With n_jobs set higher, results are always correctly ranked and correctly bounded to the size you asked for (brute_force_keep_best_n / brute_force_keep_worst_n); the only thing that can differ from a serial run is which specific combination is returned when more combinations tie exactly on score than you asked to keep – their scores are identical either way, and exact ties are rare with real-valued travel costs.

The benefit

Spreading combination evaluation across CPU cores can cut a brute-force search’s runtime several times over, particularly for the larger combination counts covered in Solving larger problems – and especially if you’re calling solve() repeatedly in the same session or long-running process (exploring several values of p, or running it as part of an app or service that stays up).

The catch: a one-off startup cost

Parallel evaluation runs each worker as a separate process. The first time you use a given n_jobs value in a session (or any call right after switching to a different n_jobs value), lokigi has to start those worker processes up, and each one has to import pandas, numpy and the rest of the scientific stack from scratch before it can do anything useful – on Windows in particular, that alone can take several seconds, regardless of how small the actual problem is. Calls that reuse the same n_jobs value reuse the already-running workers instead and pay none of that cost.

That startup cost is fixed, not proportional to problem size, so it matters most for small, one-off calls – and it bites hardest on environments with only a handful of CPU cores, such as most CI runners or budget cloud instances, where there’s little parallel work available to offset it against.

Seeing the difference in practice

Let’s put some real numbers on this, using the 4-site case from Solving larger problems – 20,475 combinations across the same 28 candidates. We’ll time it three ways: serial (n_jobs=1), a first parallel call with a fresh n_jobs=12 (paying the worker startup cost), and a second parallel call reusing the now-warm workers. We’re asking for 12 workers specifically rather than every core (n_jobs=-1), leaving a couple free for the OS and everything else running on the machine.

import os
import time

print(f"CPU cores available: {os.cpu_count()}")

CPU cores available: 20

start = time.perf_counter()
solution_serial = problem.solve(p=4, objectives="p_median", n_jobs=1, show_progress=False)
elapsed_serial = time.perf_counter() - start

start = time.perf_counter()
solution_parallel_cold = problem.solve(p=4, objectives="p_median", n_jobs=12, show_progress=False)
elapsed_parallel_cold = time.perf_counter() - start

start = time.perf_counter()
solution_parallel_warm = problem.solve(p=4, objectives="p_median", n_jobs=12, show_progress=False)
elapsed_parallel_warm = time.perf_counter() - start

All three runs agree on the best combination, exactly as the earlier section promised – n_jobs only changes how the work is spread across processes, never the result.

solution_serial.show_solutions().iloc[0]["site_indices"] == solution_parallel_warm.show_solutions().iloc[0]["site_indices"]

True

The results

import pandas as pd
import plotly.express as px

timings = pd.DataFrame({
    "run": ["Serial<br>(n_jobs=1)", "Parallel<br>first call", "Parallel<br>warm workers"],
    "elapsed_seconds": [elapsed_serial, elapsed_parallel_cold, elapsed_parallel_warm],
})
fig = px.bar(
    timings, x="run", y="elapsed_seconds",
    title="Time to brute-force 20,475 combinations (p=4, 28 candidates)",
    labels={"elapsed_seconds": "Elapsed time (seconds)", "run": ""},
    text_auto=".1f"
)
fig.update_layout(showlegend=False)
fig

Unable to display output for mime type(s): application/vnd.plotly.v1+json

Even paying the one-off worker startup cost, the first parallel call (~34s) was already about twice as fast as the serial run (~70s) – and once the workers were warm, the second parallel call (~25s) was faster still. The exact numbers will vary by machine and by how much else is competing for CPU time at the moment you run it, but the shape of the result won’t: startup cost eats into the first parallel call, and disappears from every call after it.

When it’s actually worth using

• Worth it: you’re calling solve() repeatedly in the same session or long-running process with the same n_jobs value, and your machine has a handful of genuinely idle cores.
• Probably not worth it: a single one-off call, especially for a problem small enough to finish in a couple of seconds serially anyway, or an environment with very few CPU cores – in both cases, the fixed process-startup cost is most or all of what you’d be paying for.