Add Common Optimization Methods

[jenni-niels]

This PR adds common optimization methods to the gerrychain codebase. The SingleMetricOptimizer class represents the class of optimization problems over a single plan metric and currently implements short bursts, a few variants, and tilted runs, with more to come.

The Gingleator class is a subclass of SingleMetricOptimizer and can be used to search for plans with increased numbers of Gingles' districts.

[pizzimathy]

I have no comments (for now) other than Gingleator is a great class name

[gabeschoenbach]

This looks really great! Just to check my understanding — if we called a simulated annealing run with a beta_function as something like:

gingles.hot_cold_cycle_beta_function_factory(0,1000)

(in other words only ever cold), would this be equivalent to a tilted run that always accepts better partitions, and accepts worse partitions with a dynamic probability p that depends on the beta_magnitude?

I made some small changes in docstrings, mostly just fixing some typos. I also want to flag a couple spots I think the documentation is unclear — might just be me, so would love to get other folks' input as well...

SingleMetricOptimizer optimizer.py, lines 12-25 I would change In instance of this class encapsulates the dualgraph and updaters via the initial partition to This class includes the initial partition (which gives access to the underlying dual graph and updaters).... I'm a little confused by Note that these are reset every time an optimization run is invoked and do not persist, but I'm not sure whether/how to reword that.

hot_cold_cycle_beta_function_factory optimizer.py, lines 137-144 I wonder if we can think of a more concise name for this function? And maybe add one more sentence of explanation as to its use, although I suppose this is pretty clear if you read the args on lines 140-141...

The Optimization notebook looks great! I made a small change to increase the size of the traceplots, so it's easier to see the differences in the different chains. I think it could be useful to add a little bit more documentation to the cells of the notebook, so someone could understand how the various functions work without going to the documentation. This is something I could add if you don't have the bandwidth!

[codecov-commenter]

Codecov Report

Attention: Patch coverage is 0% with 170 lines in your changes are missing coverage. Please review.

Project coverage is 80.14%. Comparing base (f2b1acd) to head (665d0ae).

:exclamation: Current head 665d0ae differs from pull request most recent head f4725de. Consider uploading reports for the commit f4725de to get more accurate results

Additional details and impacted files

@@             Coverage Diff             @@
##             main     #361       +/-   ##
===========================================
- Coverage   91.91%   80.14%   -11.77%     
===========================================
  Files          38       40        +2     
  Lines        1942     1894       -48     
===========================================
- Hits         1785     1518      -267     
- Misses        157      376      +219     

Files	Coverage Δ
gerrychain/optimization/__init__.py	0.00% <0.00%> (ø)
gerrychain/optimization/gingleator.py	0.00% <0.00%> (ø)
gerrychain/optimization/optimization.py	0.00% <0.00%> (ø)

... and 35 files with indirect coverage changes

---

Continue to review full report in Codecov by Sentry.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update f2b1acd...f4725de. Read the comment docs.

[jenni-niels]

Thanks for the review! (as well as typo catching - spelling is not my strong suit) I'll work on clarifying the documentation in the places you mentioned.

This looks really great! Just to check my understanding — if we called a simulated annealing run with a beta_function as something like:

gingles.hot_cold_cycle_beta_function_factory(0,1000)

(in other words only ever cold), would this be equivalent to a tilted run that always accepts better partitions, and accepts worse partitions with a dynamic probability p that depends on the beta_magnitude?

Yes that would be equivalent to a titled run with a dynamic probability of excepting worst scoring plans. Although, it might be simpler to simply call a simulated annealing run with beta function:

beta_function = lambda _: 1

which has slightly less computational overhead that overloading the gingles.hot_cold_cycle_beta_function_factory method.

The Optimization notebook looks great! I made a small change to increase the size of the traceplots, so it's easier to see the differences in the different chains. I think it could be useful to add a little bit more documentation to the cells of the notebook, so someone could understand how the various functions work without going to the documentation. This is something I could add if you don't have the bandwidth!

Yes I can add some more context/docs to the notebook! I'd like to expand on the pros/cons of the different optimization methods, although that might take way longer runs to show in a plot so I'm not sure if an example notebook is the place for that code. I also think it might be useful to show the usage of the SingleMetricOptimization class beyond the gingleator use case. Perhaps seeking maps that are close to aggregate proportionality or some other target? Thoughts?

[gabeschoenbach]

Definitely agree it would be good to show SingleMetricOptimization for other things — aggregate proportionality would make sense. I also was thinking it would be cool to compare/contrast all these different methods, but I think that would be best in a different file, maybe not necessarily an intro notebook. If we do do that comparison, one thing I'd love to try is just optimizing for cut edges, since for large graphs its a pretty granular metric and it would be easy to see change over time.

[gabeschoenbach]

Looks good! I just updated some stuff in the Optimization notebook so the annealing calls work with the new jumpcycle function.