This function uses redist_mergesplit() or redist_flip() to optimize a
redistrict plan according to a user-provided criteria. It does so by running
the Markov chain for "short bursts" of usually 10 iterations, and then
starting the chain anew from the best plan in the burst, according to the
criteria. This implements the ideas in the below-referenced paper, "Voting
Rights, Markov Chains, and Optimization by Short Bursts."
redist_shortburst(
map,
score_fn = NULL,
stop_at = NULL,
burst_size = ifelse(backend == "mergesplit", 10L, 50L),
max_bursts = 500L,
maximize = TRUE,
init_plan = NULL,
counties = NULL,
constraints = redist_constr(map),
compactness = 1,
adapt_k_thresh = 0.95,
reversible = TRUE,
fixed_k = NULL,
return_all = TRUE,
thin = 1L,
backend = "mergesplit",
flip_lambda = 0,
flip_eprob = 0.05,
verbose = TRUE
)A redist_map object.
A function which takes a matrix of plans and returns a score
(or, generally, a row vector) for each plan. Can also be a purrr-style
anonymous function. See ?scorers for some function factories
for common scoring rules.
A threshold to stop optimization at. When score_fn returns a
row vector per plan, maximize can be an equal-length vector specifying a
threshold for each dimension, which must all be met for the algorithm to
stop.
The size of each burst. 10 is recommended for the
mergesplit backend and 50 for the flip backend. Can also provide
burst schedule function which takes the current iteration (an integer)
and returns the desired burst size. This can be a random function.
The maximum number of bursts to run before returning.
If TRUE, try to maximize the score; otherwise, try to
minimize it. When score_fn returns a row vector per plan, maximize can
be an equal-length vector specifying whether each dimension should be
maximized or minimized.
The initial state of the map. If not provided, will default to
the reference map of the map object, or if none exists, will sample
a random initial state using redist_smc(). You can also request
a random initial state by setting init_plan="sample".
A vector containing county (or other administrative or
geographic unit) labels for each unit, which may be integers ranging from 1
to the number of counties, or a factor or character vector. If provided, the
algorithm will only generate maps which split up to ndists-1 counties.
If no county-split constraint is desired, this parameter should be left blank.
A redist_constr with Gibbs constraints.
Controls the compactness of the generated districts, with
higher values preferring more compact districts. Must be non-negative. See
redist_mergesplit for more information.
The threshold value used in the heuristic to select a
value k_i for each splitting iteration.
If FALSE and backend="mergesplit", the Markov chain
used will not be reversible. This may speed up optimization.
If not NULL, will be used to set the k parameter for the
mergesplit backend. If e.g. k=1 then the best edge in each spanning
tree will be used. Lower values may speed up optimization at the
cost of the Markov chain no longer targeting a known distribution.
Recommended only in conjunction with reversible=FALSE.
Whether to return all the burst results or just the best one (generally, the Pareto frontier). Recommended for monitoring purposes.
Save every thin-th sample. Defaults to no thinning (1). Ignored
if return_all=TRUE.
the MCMC algorithm to use within each burst, either "mergesplit" or "flip".
The parameter determining the number of swaps to attempt each iteration of flip mcmc. The number of swaps each iteration is equal to Pois(lambda) + 1. The default is 0.
The probability of keeping an edge connected in flip mcmc. The default is 0.05.
Whether to print out intermediate information while sampling. Recommended for monitoring purposes.
a redist_plans object containing the final best plan
(or the best plans after each burst, if return_all=TRUE.
Cannon, S., Goldbloom-Helzner, A., Gupta, V., Matthews, J. N., & Suwal, B. (2020). Voting Rights, Markov Chains, and Optimization by Short Bursts. arXiv preprint arXiv:2011.02288.
# \donttest{
data(iowa)
iowa_map <- redist_map(iowa, existing_plan = cd_2010, pop_tol = 0.01)
redist_shortburst(iowa_map, scorer_frac_kept(iowa_map), max_bursts = 50)
#> MERGE-SPLIT SHORT BURSTS
#> Sampling up to 50 bursts of 10 iterations each.
#> Burst Improve? score
#> 1 🙂 0.819820
#> 2 💥 0.833333
#> 5 0.833333
#> 9 ⛄ 0.842342
#> 10 0.842342
#> 15 0.842342
#> 20 0.842342
#> 25 0.842342
#> 30 0.842342
#> 34 😎 0.846847
#> 35 0.846847
#> 40 0.846847
#> 45 0.846847
#> 50 0.846847
#> A <redist_plans> containing 50 sampled plans and 1 reference plan
#> Plans have 4 districts from a 99-unit map, and were drawn using short bursts.
#> Plans matrix: int [1:99, 1:51] 1 1 2 3 4 2 2 4 2 2 ...
#> # A tibble: 204 × 5
#> draw district total_pop score burst_size
#> <fct> <int> <dbl> <dbl> <int>
#> 1 <init> 1 761612 0.820 NA
#> 2 <init> 2 761548 0.820 NA
#> 3 <init> 3 761624 0.820 NA
#> 4 <init> 4 761571 0.820 NA
#> 5 1 1 761612 0.820 10
#> 6 1 2 756911 0.820 10
#> 7 1 3 761624 0.820 10
#> 8 1 4 766208 0.820 10
#> 9 2 1 765767 0.833 10
#> 10 2 2 758388 0.833 10
#> # ℹ 194 more rows
redist_shortburst(iowa_map, ~ 1 - scorer_frac_kept(iowa_map)(.), max_bursts = 50)
#> MERGE-SPLIT SHORT BURSTS
#> Sampling up to 50 bursts of 10 iterations each.
#> Burst Improve? score
#> 1 ⛄ 0.261261
#> 5 0.261261
#> 6 🎃 0.274775
#> 10 0.274775
#> 15 0.274775
#> 20 0.274775
#> 25 0.274775
#> 30 0.274775
#> 35 0.274775
#> 40 🎆 0.279279
#> 41 💥 0.292793
#> 45 0.292793
#> 50 0.292793
#> A <redist_plans> containing 50 sampled plans and 1 reference plan
#> Plans have 4 districts from a 99-unit map, and were drawn using short bursts.
#> Plans matrix: int [1:99, 1:51] 1 1 2 3 4 2 2 4 2 2 ...
#> # A tibble: 204 × 5
#> draw district total_pop score burst_size
#> <fct> <int> <dbl> <dbl> <int>
#> 1 <init> 1 761612 0.261 NA
#> 2 <init> 2 761548 0.261 NA
#> 3 <init> 3 761624 0.261 NA
#> 4 <init> 4 761571 0.261 NA
#> 5 1 1 758566 0.261 10
#> 6 1 2 757170 0.261 10
#> 7 1 3 766755 0.261 10
#> 8 1 4 763864 0.261 10
#> 9 2 1 758566 0.261 10
#> 10 2 2 757170 0.261 10
#> # ℹ 194 more rows
# }