| n_sites_to_include | total_n_sites | combinations | |
|---|---|---|---|
| 0 | 1 | 30 | 30 |
| 1 | 2 | 30 | 435 |
| 2 | 3 | 30 | 4060 |
| 3 | 4 | 30 | 27405 |
| 4 | 5 | 30 | 142506 |
| 5 | 6 | 30 | 593775 |
| 6 | 7 | 30 | 2035800 |
| 7 | 8 | 30 | 5852925 |
| 8 | 9 | 30 | 14307150 |
| 9 | 10 | 30 | 30045015 |
| 10 | 11 | 30 | 54627300 |
| 11 | 12 | 30 | 86493225 |
| 12 | 13 | 30 | 119759850 |
| 13 | 14 | 30 | 145422675 |
| 14 | 15 | 30 | 155117520 |
| 15 | 16 | 30 | 145422675 |
| 16 | 17 | 30 | 119759850 |
| 17 | 18 | 30 | 86493225 |
| 18 | 19 | 30 | 54627300 |
| 19 | 20 | 30 | 30045015 |
| 20 | 21 | 30 | 14307150 |
| 21 | 22 | 30 | 5852925 |
| 22 | 23 | 30 | 2035800 |
| 23 | 24 | 30 | 593775 |
| 24 | 25 | 30 | 142506 |
| 25 | 26 | 30 | 27405 |
| 26 | 27 | 30 | 4060 |
| 27 | 28 | 30 | 435 |
| 28 | 29 | 30 | 30 |
Advanced Algorithms - Greedy Search and Greedy Randomized Adaptive Search Procedure (GRASP)
Brute force algorithms are effective up to a certain point, but it can quickly become impossible to evaluate all possible combinations of sites as the possible number of combinations grows very quickly.
For example, let’s imagine you have 30 possible places to put a site, but you only want 1 site. That’s 30 combinations to try.
If you want 2 sites from those 30 possibilities, that’s 435 combinations to try.
3 sites from those 30 possibilities is 4060 combinations…
4 is 27,405 combinations…
5 is 142,506 combinations…
6 is 75,287,520 combinations!
For our 30 site problem, if we want a total of 15 sites, we can see that’s nearly 160 million combinations to evaluate.
# echo: false
import plotly.express as px
px.bar(combos_df, x="n_sites_to_include", y="combinations")While we can handle the memory implications of trying to evaluate that many combinations using the keep_best_n and keep_worst_n arguments in .solve() so we’re not storing every single result, it’s still going to take an extremely long time to evaluate that many solutions.
Instead, we can turn to some different possible solutions, which we’ll explore in these notebooks.
Greedy Search
Greedy search works quite simply.
Let’s imagine we wanted to find a good solution to our n=15 problem.
We’d start by working out the best solution for 1 site (i.e. what single site gives us the best result).
We’d then take work out the best possible combination of 2 sites - where 1 site must be the site we found from the first round.
Then we keep going, repeating this process all the way up to the final number of sites.
Note
Because the greedy algorithm is short-sighted - it always takes the best possible next move - it will find a ‘good’ solution, but it may well not find the ‘best’ solution - or even one of the best.
We describe this as ‘getting stuck in a local optimum’.
from lokigi.site import SiteProblem
problem_small = SiteProblem()
problem_small.add_sites(
"../../../sample_data/brighton_sites_named.geojson",
candidate_id_col="site"
)
problem_small.add_travel_matrix(
travel_matrix_df="../../../sample_data/brighton_travel_matrix_driving_named.csv",
source_col="LSOA",
from_unit="seconds",
to_unit="minutes"
)
problem_small.add_region_geometry_layer(
"https://github.com/hsma-programme/h6_3d_facility_location_problems/raw/refs/heads/main/h6_3d_facility_location_problems/example_code/LSOA_2011_Boundaries_Super_Generalised_Clipped_BSC_EW_V4.geojson",
# "../../../sample_data/LSOA_2011_Boundaries_Super_Generalised_Clipped_BSC_EW_V4.geojson",
common_col="LSOA11NM"
)solution_small_greedy = problem_small.solve(p=3, search_strategy="greedy")/__w/lokigi/lokigi/lokigi/site.py:1370: UserWarning: No demand data was provided. Demand from all regions has been assumed to be equal.If you wish to override this, run .add_demand() to add your site dataframe before running .solve() again.You can use the .show_demand_format() to see the expected format beforehand.
warn(Best combination for 1 sites: [5]
Best combination for 2 sites: [2 5]
Best combination for 3 sites: [2 3 5]solution_small_greedy<lokigi.site_solutions.SiteSolutionSet at 0x7fb5fd3a7590>solution_small_greedy.return_best_combination_details()| index | site_names | site_indices | coverage_threshold | weighted_average | unweighted_average | 90th_percentile | max | proportion_within_coverage_threshold | problem_df | |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | None | [2, 3, 5] | None | 5.357941 | 5.357941 | 8.055933 | 16.688833 | 0.0 | LSOA L... |
solution_small_greedy.plot_best_combination()
Let’s now compare this with the best solution from our brute force approach.
solution_small_brute_force = problem_small.solve(p=3, search_strategy="brute-force")
solution_small_brute_force.plot_best_combination()
Let’s see if the solution differs with different objectives.
solution_small_greedy_p_center = problem_small.solve(p=3, search_strategy="greedy", objectives="p_center")
solution_small_greedy_p_center.plot_best_combination()Best combination for 1 sites: [2]
Best combination for 2 sites: [2 3]
Best combination for 3 sites: [2 3 5]
solution_small_greedy_mclp = problem_small.solve(p=3, search_strategy="greedy", objectives="mclp", threshold_for_coverage=8)
solution_small_greedy_mclp.plot_best_combination()Best combination for 1 sites: [5]
Best combination for 2 sites: [2 5]
Best combination for 3 sites: [2 3 5]
Interestingly, when we compare our MCLP problem (maximising coverage location problem) and p-center (minimising the maximum travel distance), we end up with the same result, but the order the sites were added in changed!
For MCLP, the best single-site combination is site index 5 (which corresponds to site 6 due to Python’s zero indexing), with site indices 2 and 3 being added in the second and third pass respectively.
In contrast, for p-center, it’s site index 2 (corresponding to site 3 - Tulip) that’s the best for a single site solution.
Greedy search on a larger problem
For the problem we’ve been working with so far, greedy search isn’t really that useful as there are a small enough number of sites that for any value of p, we can brute force (evaluate every single possible combination) without difficulty.
The value of the greedy search becomes much more apparent when we look at a bigger problem.
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")problem.total_n_sitesWith a total of 28 sites, if we were to solve for 10 sites, we would need to evaluate…
print(f"{int(math.factorial(30)/(math.factorial(30-10) * math.factorial(10))):,d}")30,045,015sites. That’s a lot of sites!
However, using the greedy algorithm, we can get a solution we can be reasonably confident is somewhat decent fairly quickly.
While we can’t pass in a maximum travel time threshold for our greedy algorithm, we can pass in the threshold_for_coverage parameter to calculate the proportion of regions that meet a given target travel time.
solution_greedy = problem.solve(p=10, search_strategy="greedy", threshold_for_coverage=10)
solution_greedy/__w/lokigi/lokigi/lokigi/site.py:1378: 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(Best combination for 1 sites: [3]
Best combination for 2 sites: [3 7]
Best combination for 3 sites: [ 3 7 11]
Best combination for 4 sites: [ 3 4 7 11]
Best combination for 5 sites: [ 3 4 7 8 11]
Best combination for 6 sites: [ 3 4 7 8 10 11]
Best combination for 7 sites: [ 3 4 7 8 10 11 22]
Best combination for 8 sites: [ 3 4 7 8 10 11 17 22]
Best combination for 9 sites: [ 3 4 7 8 10 11 17 22 24]
Best combination for 10 sites: [ 3 4 7 8 10 11 15 17 22 24]<lokigi.site_solutions.SiteSolutionSet at 0x7fb5f7290dd0>solution_greedy.show_solutions()| site_names | site_indices | coverage_threshold | weighted_average | unweighted_average | 90th_percentile | max | proportion_within_coverage_threshold | problem_df | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | None | [3, 4, 7, 8, 10, 11, 15, 17, 22, 24] | 10 | 6.81 | 10.0 | 19.43 | 32.37 | 0.61 | sector sector_x clinic_4 clinic_5 clini... |
GRASP
As we can see from the above, while we can now tackle much larger problems than before, we get a single deterministic output from the greedy search problem. This isn’t ideal - we can’t provide multiple near-optimum solutions to our stakeholders, and we have no idea how good our solution is - is it stuck in a local optimum a long way from the global optimum?
Enter GRASP - Greedy Randomised Adaptive Search Procedure.
solution = problem.solve(p=10, search_strategy="grasp", threshold_for_coverage=10)
Finding 5 diverse solutions (max 100 attempts): 0%| | 0/5 [00:00<?, ?it/s]
Finding 5 diverse solutions (max 100 attempts): 20%|██ | 1/5 [00:00<00:03, 1.27it/s]
Finding 5 diverse solutions (max 100 attempts): 40%|████ | 2/5 [00:02<00:04, 1.52s/it]
Finding 5 diverse solutions (max 100 attempts): 60%|██████ | 3/5 [00:05<00:03, 1.98s/it]
Finding 5 diverse solutions (max 100 attempts): 80%|████████ | 4/5 [00:08<00:02, 2.44s/it]
Finding 5 diverse solutions (max 100 attempts): 100%|██████████| 5/5 [00:11<00:00, 2.55s/it]
Finding 5 diverse solutions (max 100 attempts): 100%|██████████| 5/5 [00:11<00:00, 2.25s/it]solution.show_solutions()| site_names | site_indices | coverage_threshold | weighted_average | unweighted_average | 90th_percentile | max | proportion_within_coverage_threshold | problem_df | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | None | [3, 4, 5, 8, 10, 11, 15, 17, 22, 24] | 10 | 6.79 | 9.89 | 18.68 | 32.37 | 0.62 | sector sector_x clinic_4 clinic_5 clini... |
| 1 | None | [3, 4, 5, 8, 9, 11, 12, 17, 22, 24] | 10 | 6.86 | 10.09 | 20.35 | 32.37 | 0.62 | sector sector_x clinic_4 clinic_5 clini... |
| 2 | None | [3, 4, 5, 8, 9, 11, 12, 17, 22, 27] | 10 | 6.88 | 10.06 | 20.11 | 32.37 | 0.61 | sector sector_x clinic_4 clinic_5 clini... |
| 3 | None | [0, 4, 5, 8, 9, 11, 12, 17, 22, 27] | 10 | 6.91 | 10.21 | 20.11 | 32.37 | 0.60 | sector sector_x clinic_1 clinic_5 clini... |
| 4 | None | [0, 4, 7, 8, 9, 10, 11, 17, 22, 27] | 10 | 7.00 | 10.38 | 20.58 | 32.37 | 0.58 | sector sector_x clinic_1 clinic_5 clini... |
Let’s compare this to the best solution found by the pure greedy algorithm:
solution_greedy.show_solutions()| site_names | site_indices | coverage_threshold | weighted_average | unweighted_average | 90th_percentile | max | proportion_within_coverage_threshold | problem_df | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | None | [3, 4, 7, 8, 10, 11, 15, 17, 22, 24] | 10 | 6.81 | 10.0 | 19.43 | 32.37 | 0.61 | sector sector_x clinic_4 clinic_5 clini... |
Interestingly this doesn’t show up in our top 5 solutions found with GRASP, and is between the top two solutions that were found! So it’s worth considering whether to run both.
We can try to run GRASP with a higher number of maximum iterations and a slightly higher alpha to get a more diverse solution pool. In the interests of it not taking forever to regenerate this documentation, below we show a screenshot of the outputs when we’ve run GRASP for much longer.
solution_grasp_big = problem.solve(
p=10, search_strategy="grasp", threshold_for_coverage=10, grasp_alpha=0.6,
grasp_max_attempts=50000, grasp_num_solutions=50
)
Finding 50 diverse solutions (max 50000 attempts): 0%| | 0/50 [00:00<?, ?it/s]
Finding 50 diverse solutions (max 50000 attempts): 2%|▏ | 1/50 [00:00<00:46, 1.06it/s]
Finding 50 diverse solutions (max 50000 attempts): 4%|▍ | 2/50 [00:03<01:43, 2.15s/it]
Finding 50 diverse solutions (max 50000 attempts): 6%|▌ | 3/50 [00:05<01:33, 1.99s/it]
Finding 50 diverse solutions (max 50000 attempts): 8%|▊ | 4/50 [00:06<01:07, 1.47s/it]
Finding 50 diverse solutions (max 50000 attempts): 10%|█ | 5/50 [00:09<01:29, 1.99s/it]
Finding 50 diverse solutions (max 50000 attempts): 12%|█▏ | 6/50 [00:11<01:29, 2.03s/it]
Finding 50 diverse solutions (max 50000 attempts): 14%|█▍ | 7/50 [00:16<02:06, 2.94s/it]
Finding 50 diverse solutions (max 50000 attempts): 16%|█▌ | 8/50 [00:16<01:31, 2.18s/it]
Finding 50 diverse solutions (max 50000 attempts): 18%|█▊ | 9/50 [00:18<01:23, 2.03s/it]
Finding 50 diverse solutions (max 50000 attempts): 20%|██ | 10/50 [00:26<02:29, 3.74s/it]
Finding 50 diverse solutions (max 50000 attempts): 22%|██▏ | 11/50 [00:28<02:07, 3.26s/it]
Finding 50 diverse solutions (max 50000 attempts): 24%|██▍ | 12/50 [00:31<02:03, 3.26s/it]
Finding 50 diverse solutions (max 50000 attempts): 26%|██▌ | 13/50 [00:36<02:20, 3.80s/it]
Finding 50 diverse solutions (max 50000 attempts): 28%|██▊ | 14/50 [00:37<01:49, 3.03s/it]
Finding 50 diverse solutions (max 50000 attempts): 30%|███ | 15/50 [00:49<03:17, 5.63s/it]
Finding 50 diverse solutions (max 50000 attempts): 32%|███▏ | 16/50 [00:53<02:51, 5.03s/it]
Finding 50 diverse solutions (max 50000 attempts): 34%|███▍ | 17/50 [00:54<02:12, 4.02s/it]
Finding 50 diverse solutions (max 50000 attempts): 36%|███▌ | 18/50 [00:56<01:46, 3.34s/it]
Finding 50 diverse solutions (max 50000 attempts): 38%|███▊ | 19/50 [00:59<01:37, 3.14s/it]
Finding 50 diverse solutions (max 50000 attempts): 40%|████ | 20/50 [01:01<01:25, 2.85s/it]
Finding 50 diverse solutions (max 50000 attempts): 42%|████▏ | 21/50 [01:01<01:02, 2.15s/it]
Finding 50 diverse solutions (max 50000 attempts): 44%|████▍ | 22/50 [01:02<00:46, 1.67s/it]
Finding 50 diverse solutions (max 50000 attempts): 46%|████▌ | 23/50 [01:03<00:36, 1.35s/it]
Finding 50 diverse solutions (max 50000 attempts): 48%|████▊ | 24/50 [01:07<00:59, 2.30s/it]
Finding 50 diverse solutions (max 50000 attempts): 50%|█████ | 25/50 [01:10<01:02, 2.49s/it]
Finding 50 diverse solutions (max 50000 attempts): 52%|█████▏ | 26/50 [01:11<00:51, 2.15s/it]
Finding 50 diverse solutions (max 50000 attempts): 54%|█████▍ | 27/50 [01:14<00:49, 2.17s/it]
Finding 50 diverse solutions (max 50000 attempts): 56%|█████▌ | 28/50 [01:15<00:40, 1.82s/it]
Finding 50 diverse solutions (max 50000 attempts): 58%|█████▊ | 29/50 [01:15<00:30, 1.43s/it]
Finding 50 diverse solutions (max 50000 attempts): 60%|██████ | 30/50 [01:20<00:49, 2.49s/it]
Finding 50 diverse solutions (max 50000 attempts): 62%|██████▏ | 31/50 [01:22<00:41, 2.20s/it]
Finding 50 diverse solutions (max 50000 attempts): 64%|██████▍ | 32/50 [01:29<01:05, 3.64s/it]
Finding 50 diverse solutions (max 50000 attempts): 66%|██████▌ | 33/50 [01:31<00:56, 3.30s/it]
Finding 50 diverse solutions (max 50000 attempts): 68%|██████▊ | 34/50 [01:38<01:11, 4.48s/it]
Finding 50 diverse solutions (max 50000 attempts): 70%|███████ | 35/50 [01:42<01:04, 4.28s/it]
Finding 50 diverse solutions (max 50000 attempts): 72%|███████▏ | 36/50 [01:44<00:50, 3.59s/it]
Finding 50 diverse solutions (max 50000 attempts): 74%|███████▍ | 37/50 [01:45<00:35, 2.70s/it]
Finding 50 diverse solutions (max 50000 attempts): 76%|███████▌ | 38/50 [01:50<00:42, 3.57s/it]
Finding 50 diverse solutions (max 50000 attempts): 78%|███████▊ | 39/50 [01:52<00:31, 2.89s/it]
Finding 50 diverse solutions (max 50000 attempts): 80%|████████ | 40/50 [01:53<00:23, 2.39s/it]
Finding 50 diverse solutions (max 50000 attempts): 82%|████████▏ | 41/50 [01:55<00:20, 2.24s/it]
Finding 50 diverse solutions (max 50000 attempts): 84%|████████▍ | 42/50 [01:56<00:16, 2.02s/it]
Finding 50 diverse solutions (max 50000 attempts): 86%|████████▌ | 43/50 [01:59<00:15, 2.14s/it]
Finding 50 diverse solutions (max 50000 attempts): 88%|████████▊ | 44/50 [02:02<00:14, 2.43s/it]
Finding 50 diverse solutions (max 50000 attempts): 90%|█████████ | 45/50 [02:07<00:15, 3.18s/it]
Finding 50 diverse solutions (max 50000 attempts): 92%|█████████▏| 46/50 [02:08<00:10, 2.53s/it]
Finding 50 diverse solutions (max 50000 attempts): 94%|█████████▍| 47/50 [02:08<00:05, 1.98s/it]
Finding 50 diverse solutions (max 50000 attempts): 96%|█████████▌| 48/50 [02:09<00:03, 1.54s/it]
Finding 50 diverse solutions (max 50000 attempts): 98%|█████████▊| 49/50 [02:13<00:02, 2.43s/it]
Finding 50 diverse solutions (max 50000 attempts): 100%|██████████| 50/50 [02:16<00:00, 2.62s/it]
Finding 50 diverse solutions (max 50000 attempts): 100%|██████████| 50/50 [02:16<00:00, 2.74s/it]solution_grasp_big.show_solutions().head(10)| site_names | site_indices | coverage_threshold | weighted_average | unweighted_average | 90th_percentile | max | proportion_within_coverage_threshold | problem_df | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | None | [3, 4, 5, 8, 10, 11, 15, 17, 22, 24] | 10 | 6.79 | 9.89 | 18.68 | 32.37 | 0.62 | sector sector_x clinic_4 clinic_5 clini... |
| 1 | None | [3, 4, 7, 8, 10, 11, 15, 17, 22, 24] | 10 | 6.81 | 10.00 | 19.43 | 32.37 | 0.61 | sector sector_x clinic_4 clinic_5 clini... |
| 2 | None | [3, 4, 5, 8, 10, 11, 15, 17, 22, 27] | 10 | 6.82 | 9.89 | 18.21 | 32.37 | 0.61 | sector sector_x clinic_4 clinic_5 clini... |
| 3 | None | [1, 3, 4, 5, 8, 10, 11, 15, 17, 22] | 10 | 6.82 | 9.90 | 18.30 | 32.37 | 0.61 | sector sector_x clinic_2 clinic_4 clini... |
| 4 | None | [3, 4, 5, 8, 10, 11, 14, 17, 22, 24] | 10 | 6.83 | 9.88 | 19.45 | 32.37 | 0.62 | sector sector_x clinic_4 clinic_5 clini... |
| 5 | None | [3, 4, 6, 7, 8, 10, 11, 17, 22, 24] | 10 | 6.83 | 10.09 | 20.08 | 32.37 | 0.61 | sector sector_x clinic_4 clinic_5 clini... |
| 6 | None | [0, 3, 4, 5, 8, 10, 11, 17, 22, 27] | 10 | 6.84 | 10.06 | 20.11 | 32.37 | 0.60 | sector sector_x clinic_1 clinic_4 clini... |
| 7 | None | [0, 1, 3, 4, 5, 8, 10, 11, 17, 22] | 10 | 6.84 | 10.08 | 20.11 | 32.37 | 0.60 | sector sector_x clinic_1 clinic_2 clini... |
| 8 | None | [3, 4, 7, 8, 10, 11, 14, 17, 22, 24] | 10 | 6.84 | 9.95 | 19.53 | 32.37 | 0.61 | sector sector_x clinic_4 clinic_5 clini... |
| 9 | None | [3, 4, 5, 7, 8, 10, 11, 17, 22, 24] | 10 | 6.85 | 10.14 | 20.44 | 32.37 | 0.61 | sector sector_x clinic_4 clinic_5 clini... |
Other GRASP parameters
We can change the number of sites that must differ to force a more diverse pool of solutions.
solution_grasp_big_more_diverse = problem.solve(
p=10, search_strategy="grasp", threshold_for_coverage=10, grasp_alpha=0.6,
grasp_max_attempts=50000, grasp_num_solutions=30,
grasp_min_sites_different=4, # set this value - default is 1
)
Finding 30 diverse solutions (max 50000 attempts): 0%| | 0/30 [00:00<?, ?it/s]
Finding 30 diverse solutions (max 50000 attempts): 3%|▎ | 1/30 [00:00<00:27, 1.05it/s]
Finding 30 diverse solutions (max 50000 attempts): 7%|▋ | 2/30 [00:04<01:01, 2.19s/it]
Finding 30 diverse solutions (max 50000 attempts): 10%|█ | 3/30 [00:06<01:02, 2.32s/it]
Finding 30 diverse solutions (max 50000 attempts): 13%|█▎ | 4/30 [00:09<01:06, 2.56s/it]
Finding 30 diverse solutions (max 50000 attempts): 17%|█▋ | 5/30 [00:11<01:00, 2.40s/it]
Finding 30 diverse solutions (max 50000 attempts): 20%|██ | 6/30 [00:18<01:35, 3.97s/it]
Finding 30 diverse solutions (max 50000 attempts): 23%|██▎ | 7/30 [00:25<01:54, 4.98s/it]
Finding 30 diverse solutions (max 50000 attempts): 27%|██▋ | 8/30 [00:28<01:33, 4.24s/it]
Finding 30 diverse solutions (max 50000 attempts): 30%|███ | 9/30 [00:31<01:22, 3.92s/it]
Finding 30 diverse solutions (max 50000 attempts): 33%|███▎ | 10/30 [00:49<02:44, 8.23s/it]
Finding 30 diverse solutions (max 50000 attempts): 37%|███▋ | 11/30 [00:52<02:09, 6.82s/it]
Finding 30 diverse solutions (max 50000 attempts): 40%|████ | 12/30 [00:56<01:44, 5.80s/it]
Finding 30 diverse solutions (max 50000 attempts): 43%|████▎ | 13/30 [00:59<01:22, 4.86s/it]
Finding 30 diverse solutions (max 50000 attempts): 47%|████▋ | 14/30 [01:01<01:04, 4.02s/it]
Finding 30 diverse solutions (max 50000 attempts): 50%|█████ | 15/30 [01:01<00:44, 2.98s/it]
Finding 30 diverse solutions (max 50000 attempts): 53%|█████▎ | 16/30 [01:02<00:31, 2.27s/it]
Finding 30 diverse solutions (max 50000 attempts): 57%|█████▋ | 17/30 [01:07<00:40, 3.13s/it]
Finding 30 diverse solutions (max 50000 attempts): 60%|██████ | 18/30 [01:10<00:36, 3.08s/it]
Finding 30 diverse solutions (max 50000 attempts): 63%|██████▎ | 19/30 [01:14<00:35, 3.22s/it]
Finding 30 diverse solutions (max 50000 attempts): 67%|██████▋ | 20/30 [01:15<00:27, 2.71s/it]
Finding 30 diverse solutions (max 50000 attempts): 70%|███████ | 21/30 [01:31<01:00, 6.67s/it]
Finding 30 diverse solutions (max 50000 attempts): 73%|███████▎ | 22/30 [01:55<01:33, 11.75s/it]
Finding 30 diverse solutions (max 50000 attempts): 77%|███████▋ | 23/30 [01:59<01:05, 9.41s/it]
Finding 30 diverse solutions (max 50000 attempts): 80%|████████ | 24/30 [02:02<00:45, 7.51s/it]
Finding 30 diverse solutions (max 50000 attempts): 83%|████████▎ | 25/30 [02:08<00:36, 7.24s/it]
Finding 30 diverse solutions (max 50000 attempts): 87%|████████▋ | 26/30 [02:09<00:20, 5.23s/it]
Finding 30 diverse solutions (max 50000 attempts): 90%|█████████ | 27/30 [02:13<00:14, 5.00s/it]
Finding 30 diverse solutions (max 50000 attempts): 93%|█████████▎| 28/30 [02:16<00:08, 4.41s/it]
Finding 30 diverse solutions (max 50000 attempts): 97%|█████████▋| 29/30 [02:33<00:07, 7.97s/it]
Finding 30 diverse solutions (max 50000 attempts): 100%|██████████| 30/30 [02:38<00:00, 7.17s/it]
Finding 30 diverse solutions (max 50000 attempts): 100%|██████████| 30/30 [02:38<00:00, 5.28s/it]solution_grasp_big_more_diverse.show_solutions().head(10)| site_names | site_indices | coverage_threshold | weighted_average | unweighted_average | 90th_percentile | max | proportion_within_coverage_threshold | problem_df | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | None | [3, 4, 6, 7, 8, 10, 11, 17, 22, 24] | 10 | 6.83 | 10.09 | 20.08 | 32.37 | 0.61 | sector sector_x clinic_4 clinic_5 clini... |
| 1 | None | [0, 3, 4, 5, 8, 10, 11, 17, 22, 27] | 10 | 6.84 | 10.06 | 20.11 | 32.37 | 0.60 | sector sector_x clinic_1 clinic_4 clini... |
| 2 | None | [3, 4, 5, 8, 9, 11, 12, 17, 22, 24] | 10 | 6.86 | 10.09 | 20.35 | 32.37 | 0.62 | sector sector_x clinic_4 clinic_5 clini... |
| 3 | None | [0, 1, 2, 4, 6, 8, 10, 11, 17, 22] | 10 | 6.98 | 10.20 | 20.12 | 32.37 | 0.59 | sector sector_x clinic_1 clinic_2 clini... |
| 4 | None | [1, 3, 4, 5, 8, 10, 11, 15, 22, 24] | 10 | 7.04 | 10.48 | 18.62 | 32.37 | 0.56 | sector sector_x clinic_2 clinic_4 clini... |
| 5 | None | [0, 1, 4, 7, 8, 10, 11, 13, 14, 22] | 10 | 7.07 | 10.17 | 18.66 | 32.37 | 0.59 | sector sector_x clinic_1 clinic_2 clini... |
| 6 | None | [2, 4, 5, 8, 10, 11, 13, 14, 22, 24] | 10 | 7.08 | 10.06 | 19.45 | 32.37 | 0.63 | sector sector_x clinic_3 clinic_5 clini... |
| 7 | None | [0, 2, 4, 7, 11, 12, 17, 21, 22, 24] | 10 | 7.17 | 10.47 | 20.58 | 32.37 | 0.58 | sector sector_x clinic_1 clinic_3 clini... |
| 8 | None | [3, 4, 5, 6, 10, 11, 13, 21, 22, 27] | 10 | 7.18 | 10.12 | 19.96 | 32.37 | 0.60 | sector sector_x clinic_4 clinic_5 clini... |
| 9 | None | [0, 1, 4, 6, 7, 8, 9, 11, 12, 17] | 10 | 7.22 | 10.87 | 22.03 | 32.37 | 0.56 | sector sector_x clinic_1 clinic_2 clini... |
We can also change the chance of a local search taking place.
solution_grasp_less_local_searching = problem.solve(
p=10, search_strategy="grasp", threshold_for_coverage=10, grasp_alpha=0.6,
grasp_max_attempts=50000, grasp_num_solutions=20,
grasp_local_search_chance=0.4 # set this value - default is 0.8
)
Finding 20 diverse solutions (max 50000 attempts): 0%| | 0/20 [00:00<?, ?it/s]
Finding 20 diverse solutions (max 50000 attempts): 5%|▌ | 1/20 [00:00<00:18, 1.05it/s]
Finding 20 diverse solutions (max 50000 attempts): 10%|█ | 2/20 [00:01<00:14, 1.23it/s]
Finding 20 diverse solutions (max 50000 attempts): 15%|█▌ | 3/20 [00:03<00:24, 1.46s/it]
Finding 20 diverse solutions (max 50000 attempts): 20%|██ | 4/20 [00:04<00:18, 1.16s/it]
Finding 20 diverse solutions (max 50000 attempts): 25%|██▌ | 5/20 [00:05<00:14, 1.01it/s]
Finding 20 diverse solutions (max 50000 attempts): 30%|███ | 6/20 [00:05<00:12, 1.13it/s]
Finding 20 diverse solutions (max 50000 attempts): 35%|███▌ | 7/20 [00:09<00:20, 1.60s/it]
Finding 20 diverse solutions (max 50000 attempts): 40%|████ | 8/20 [00:11<00:23, 1.94s/it]
Finding 20 diverse solutions (max 50000 attempts): 45%|████▌ | 9/20 [00:12<00:16, 1.51s/it]
Finding 20 diverse solutions (max 50000 attempts): 50%|█████ | 10/20 [00:14<00:16, 1.66s/it]
Finding 20 diverse solutions (max 50000 attempts): 55%|█████▌ | 11/20 [00:16<00:15, 1.73s/it]
Finding 20 diverse solutions (max 50000 attempts): 60%|██████ | 12/20 [00:16<00:11, 1.39s/it]
Finding 20 diverse solutions (max 50000 attempts): 65%|██████▌ | 13/20 [00:17<00:08, 1.17s/it]
Finding 20 diverse solutions (max 50000 attempts): 70%|███████ | 14/20 [00:18<00:05, 1.01it/s]
Finding 20 diverse solutions (max 50000 attempts): 75%|███████▌ | 15/20 [00:18<00:04, 1.12it/s]
Finding 20 diverse solutions (max 50000 attempts): 80%|████████ | 16/20 [00:19<00:03, 1.11it/s]
Finding 20 diverse solutions (max 50000 attempts): 85%|████████▌ | 17/20 [00:21<00:03, 1.26s/it]
Finding 20 diverse solutions (max 50000 attempts): 90%|█████████ | 18/20 [00:24<00:03, 1.63s/it]
Finding 20 diverse solutions (max 50000 attempts): 95%|█████████▌| 19/20 [00:27<00:02, 2.02s/it]
Finding 20 diverse solutions (max 50000 attempts): 100%|██████████| 20/20 [00:27<00:00, 1.59s/it]
Finding 20 diverse solutions (max 50000 attempts): 100%|██████████| 20/20 [00:27<00:00, 1.38s/it]And we can also change the maximum number of swaps that will happen in the local search stage, ensuring a diverse range of solutions is explored, which is particularly important for larger questions.
solution_grasp_less_local_searching = problem.solve(
p=10, search_strategy="grasp", threshold_for_coverage=10, grasp_alpha=0.6,
grasp_max_attempts=50000, grasp_num_solutions=20,
grasp_max_swap_count_local_search=50 # set this value - default is 10
)
Finding 20 diverse solutions (max 50000 attempts): 0%| | 0/20 [00:00<?, ?it/s]
Finding 20 diverse solutions (max 50000 attempts): 5%|▌ | 1/20 [00:00<00:14, 1.27it/s]
Finding 20 diverse solutions (max 50000 attempts): 10%|█ | 2/20 [00:05<00:52, 2.90s/it]
Finding 20 diverse solutions (max 50000 attempts): 15%|█▌ | 3/20 [00:07<00:42, 2.51s/it]
Finding 20 diverse solutions (max 50000 attempts): 20%|██ | 4/20 [00:13<01:01, 3.86s/it]
Finding 20 diverse solutions (max 50000 attempts): 25%|██▌ | 5/20 [00:17<01:02, 4.18s/it]
Finding 20 diverse solutions (max 50000 attempts): 30%|███ | 6/20 [00:18<00:41, 2.95s/it]
Finding 20 diverse solutions (max 50000 attempts): 35%|███▌ | 7/20 [00:27<01:05, 5.03s/it]
Finding 20 diverse solutions (max 50000 attempts): 40%|████ | 8/20 [00:34<01:07, 5.59s/it]
Finding 20 diverse solutions (max 50000 attempts): 45%|████▌ | 9/20 [00:55<01:53, 10.31s/it]
Finding 20 diverse solutions (max 50000 attempts): 50%|█████ | 10/20 [00:59<01:22, 8.29s/it]
Finding 20 diverse solutions (max 50000 attempts): 55%|█████▌ | 11/20 [01:02<01:00, 6.76s/it]
Finding 20 diverse solutions (max 50000 attempts): 60%|██████ | 12/20 [01:04<00:43, 5.48s/it]
Finding 20 diverse solutions (max 50000 attempts): 65%|██████▌ | 13/20 [01:05<00:27, 4.00s/it]
Finding 20 diverse solutions (max 50000 attempts): 70%|███████ | 14/20 [01:06<00:17, 2.97s/it]
Finding 20 diverse solutions (max 50000 attempts): 75%|███████▌ | 15/20 [01:10<00:16, 3.37s/it]
Finding 20 diverse solutions (max 50000 attempts): 80%|████████ | 16/20 [01:13<00:12, 3.16s/it]
Finding 20 diverse solutions (max 50000 attempts): 85%|████████▌ | 17/20 [01:19<00:12, 4.08s/it]
Finding 20 diverse solutions (max 50000 attempts): 90%|█████████ | 18/20 [01:33<00:14, 7.05s/it]
Finding 20 diverse solutions (max 50000 attempts): 95%|█████████▌| 19/20 [01:35<00:05, 5.67s/it]
Finding 20 diverse solutions (max 50000 attempts): 100%|██████████| 20/20 [01:41<00:00, 5.81s/it]
Finding 20 diverse solutions (max 50000 attempts): 100%|██████████| 20/20 [01:41<00:00, 5.09s/it]GRASP on our smaller problem - does it find the known optimal solution in this case?
Let’s also try this out on our smaller problem from earlier - do we find the optimal solution here too?
solution_small_grasp = problem_small.solve(p=3, search_strategy="grasp")
Finding 5 diverse solutions (max 20 attempts): 0%| | 0/5 [00:00<?, ?it/s]
Finding 5 diverse solutions (max 20 attempts): 40%|████ | 2/5 [00:00<00:00, 21.49it/s]
/__w/lokigi/lokigi/lokigi/site.py:1606: UserWarning: GRASP exhausted attempt budget (20 attempts) before finding 5 sufficiently diverse solutions. Returning 2 solutions.
outputs = self._grasp(solution_small_grasp.show_solutions()| site_names | site_indices | coverage_threshold | weighted_average | unweighted_average | 90th_percentile | max | proportion_within_coverage_threshold | problem_df | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | None | [2, 3, 5] | None | 5.36 | 5.36 | 8.06 | 16.69 | 0.0 | LSOA L... |
| 1 | None | [2, 3, 4] | None | 5.45 | 5.45 | 8.50 | 16.69 | 0.0 | LSOA L... |
solution_small_grasp.plot_best_combination()
It gets quite stuck with the default alpha value, finding only two solutions! Let’s turn up the alpha and see if we can get some more varied solutions out.
solution_small_grasp_higher_alpha = problem_small.solve(
p=3, search_strategy="grasp",
grasp_alpha=0.4, grasp_max_attempts=500
)
Finding 5 diverse solutions (max 500 attempts): 0%| | 0/5 [00:00<?, ?it/s]
Finding 5 diverse solutions (max 500 attempts): 40%|████ | 2/5 [00:00<00:00, 18.32it/s]
Finding 5 diverse solutions (max 500 attempts): 40%|████ | 2/5 [00:00<00:00, 16.17it/s]
/__w/lokigi/lokigi/lokigi/site.py:1606: UserWarning: GRASP exhausted attempt budget (500 attempts) before finding 5 sufficiently diverse solutions. Returning 2 solutions.
outputs = self._grasp(solution_small_grasp_higher_alpha.show_solutions()| site_names | site_indices | coverage_threshold | weighted_average | unweighted_average | 90th_percentile | max | proportion_within_coverage_threshold | problem_df | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | None | [2, 3, 5] | None | 5.36 | 5.36 | 8.06 | 16.69 | 0.0 | LSOA L... |
| 1 | None | [2, 3, 4] | None | 5.45 | 5.45 | 8.50 | 16.69 | 0.0 | LSOA L... |
It looks like we need to make our alpha higher again!
solution_small_grasp_even_higher_alpha = problem_small.solve(
p=3, search_strategy="grasp",
grasp_alpha=0.6, grasp_max_attempts=100000,
grasp_min_sites_different=1
)
Finding 5 diverse solutions (max 100000 attempts): 0%| | 0/5 [00:00<?, ?it/s]
Finding 5 diverse solutions (max 100000 attempts): 60%|██████ | 3/5 [00:00<00:00, 22.70it/s]
Finding 5 diverse solutions (max 100000 attempts): 100%|██████████| 5/5 [00:00<00:00, 34.75it/s]solution_small_grasp_even_higher_alpha.show_solutions()| site_names | site_indices | coverage_threshold | weighted_average | unweighted_average | 90th_percentile | max | proportion_within_coverage_threshold | problem_df | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | None | [2, 3, 5] | None | 5.36 | 5.36 | 8.06 | 16.69 | 0.0 | LSOA L... |
| 1 | None | [2, 3, 4] | None | 5.45 | 5.45 | 8.50 | 16.69 | 0.0 | LSOA L... |
| 2 | None | [1, 2, 3] | None | 5.59 | 5.59 | 9.00 | 16.69 | 0.0 | LSOA L... |
| 3 | None | [1, 3, 5] | None | 6.64 | 6.64 | 11.58 | 22.86 | 0.0 | LSOA L... |
| 4 | None | [3, 4, 5] | None | 6.73 | 6.73 | 12.26 | 21.71 | 0.0 | LSOA L... |
Let’s compare this with the best solutions from the brute force approach.
solution_small_brute_force.show_solutions().head(15)| site_names | site_indices | coverage_threshold | weighted_average | unweighted_average | 90th_percentile | max | proportion_within_coverage_threshold | problem_df | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | None | [2, 3, 5] | None | 5.36 | 5.36 | 8.06 | 16.69 | 0.0 | LSOA L... |
| 1 | None | [2, 3, 4] | None | 5.45 | 5.45 | 8.50 | 16.69 | 0.0 | LSOA L... |
| 2 | None | [1, 2, 3] | None | 5.59 | 5.59 | 9.00 | 16.69 | 0.0 | LSOA L... |
| 3 | None | [0, 2, 3] | None | 5.67 | 5.67 | 9.36 | 16.69 | 0.0 | LSOA L... |
| 4 | None | [0, 2, 5] | None | 6.21 | 6.21 | 9.33 | 16.69 | 0.0 | LSOA L... |
| 5 | None | [2, 4, 5] | None | 6.29 | 6.29 | 9.26 | 16.69 | 0.0 | LSOA L... |
| 6 | None | [1, 2, 5] | None | 6.31 | 6.31 | 9.45 | 16.69 | 0.0 | LSOA L... |
| 7 | None | [0, 2, 4] | None | 6.32 | 6.32 | 9.70 | 16.69 | 0.0 | LSOA L... |
| 8 | None | [0, 1, 2] | None | 6.39 | 6.39 | 9.77 | 16.69 | 0.0 | LSOA L... |
| 9 | None | [1, 3, 5] | None | 6.64 | 6.64 | 11.58 | 22.86 | 0.0 | LSOA L... |
| 10 | None | [3, 4, 5] | None | 6.73 | 6.73 | 12.26 | 21.71 | 0.0 | LSOA L... |
| 11 | None | [1, 3, 4] | None | 6.76 | 6.76 | 11.32 | 21.71 | 0.0 | LSOA L... |
| 12 | None | [0, 3, 4] | None | 6.81 | 6.81 | 12.26 | 21.71 | 0.0 | LSOA L... |
| 13 | None | [0, 1, 3] | None | 6.92 | 6.92 | 11.93 | 23.92 | 0.0 | LSOA L... |
| 14 | None | [1, 2, 4] | None | 7.46 | 7.46 | 11.57 | 16.69 | 0.0 | LSOA L... |
We can see it found the - best - second best - 3rd best - 10th best - and 11th best solutions
Let’s go with an even higher alpha and ask for it to find more solutions.
solution_small_grasp_higher_alpha_more_sols = problem_small.solve(
p=3, search_strategy="grasp",
grasp_alpha=0.95, grasp_max_attempts=50000,
grasp_num_solutions=20
)
Finding 20 diverse solutions (max 50000 attempts): 0%| | 0/20 [00:00<?, ?it/s]
Finding 20 diverse solutions (max 50000 attempts): 15%|█▌ | 3/20 [00:00<00:00, 22.59it/s]
Finding 20 diverse solutions (max 50000 attempts): 75%|███████▌ | 15/20 [00:02<00:00, 7.42it/s]
/__w/lokigi/lokigi/lokigi/site.py:1606: UserWarning: GRASP exhausted attempt budget (50000 attempts) before finding 20 sufficiently diverse solutions. Returning 15 solutions.
outputs = self._grasp(solution_small_grasp_higher_alpha_more_sols.show_solutions()| site_names | site_indices | coverage_threshold | weighted_average | unweighted_average | 90th_percentile | max | proportion_within_coverage_threshold | problem_df | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | None | [2, 3, 5] | None | 5.36 | 5.36 | 8.06 | 16.69 | 0.0 | LSOA L... |
| 1 | None | [2, 3, 4] | None | 5.45 | 5.45 | 8.50 | 16.69 | 0.0 | LSOA L... |
| 2 | None | [1, 2, 3] | None | 5.59 | 5.59 | 9.00 | 16.69 | 0.0 | LSOA L... |
| 3 | None | [0, 2, 3] | None | 5.67 | 5.67 | 9.36 | 16.69 | 0.0 | LSOA L... |
| 4 | None | [0, 2, 5] | None | 6.21 | 6.21 | 9.33 | 16.69 | 0.0 | LSOA L... |
| 5 | None | [2, 4, 5] | None | 6.29 | 6.29 | 9.26 | 16.69 | 0.0 | LSOA L... |
| 6 | None | [1, 2, 5] | None | 6.31 | 6.31 | 9.45 | 16.69 | 0.0 | LSOA L... |
| 7 | None | [0, 2, 4] | None | 6.32 | 6.32 | 9.70 | 16.69 | 0.0 | LSOA L... |
| 8 | None | [0, 1, 2] | None | 6.39 | 6.39 | 9.77 | 16.69 | 0.0 | LSOA L... |
| 9 | None | [1, 3, 5] | None | 6.64 | 6.64 | 11.58 | 22.86 | 0.0 | LSOA L... |
| 10 | None | [3, 4, 5] | None | 6.73 | 6.73 | 12.26 | 21.71 | 0.0 | LSOA L... |
| 11 | None | [1, 3, 4] | None | 6.76 | 6.76 | 11.32 | 21.71 | 0.0 | LSOA L... |
| 12 | None | [0, 3, 4] | None | 6.81 | 6.81 | 12.26 | 21.71 | 0.0 | LSOA L... |
| 13 | None | [0, 1, 3] | None | 6.92 | 6.92 | 11.93 | 23.92 | 0.0 | LSOA L... |
| 14 | None | [0, 1, 5] | None | 7.54 | 7.54 | 11.90 | 22.86 | 0.0 | LSOA L... |
With an even higher alpha, we could choose to run for longer periods and be confident we’re exploring a good range of the solution space without the computational overhead of the brute force method.