Examples on how to generate political districting plans. All codes are written using Python, with NetworkX used for handling graphs, Gurobi used as MIP solver, and GeoPandas used to draw maps. Used in an undergraduate Operations Research course at Oklahoma State University (IEM 4013).
The MIP models are summarized in Two_districting_models.pdf.
The Oklahoma county graph is duplicated from Daryl DeFord's page, which has graphs for other states and other levels (e.g., census tracts, census blocks, etc). These files contain other data (e.g., demographic data) besides the graph itself. The Oklahoma shapefiles are duplicated from Eugene Lykhovyd's page, which has other states too.
It is possible to download the files individually, but the naming conventions are different. Daryl uses FIPS codes while Eugene uses postal codes. So, Daryl's Oklahoma county file is called COUNTY_40.json while Eugene's are called OK_counties.shp (shx,prj,...).
A clean way to get both datasets with intuitive names (e.g., OK_county.json and OK_county.shp) is to run my data downloaders. They download the data for all 50 states and store them in the directory C://districting-data-2010//
The input data is typically read using the GerryChain package. It can sometimes be difficult to install GerryChain. Here is a tutorial video if you run into problems.
D1-Min-Deviation.ipynb shows how to:
- read county populations from a text file
- build a MIP model in Gurobi to minimize population deviation
D2-Min-Cut-Edges.ipynb shows how to:
- read a graph from a file (using NetworkX)
- build a MIP model in Gurobi to minimize cut edges
- check if the resulting districts are connected (using NetworkX)
D3-Min-Cut-Edges-with-GeoPandas.ipynb shows how to:
- read a graph from a .json file (using the GerryChain reader)
- print the names of the counties and their populations
- build a MIP model in Gurobi to minimize cut edges
- read a shapefile with GeoPandas
- draw the districting plan on a map with GeoPandas
D4-Min-Cut-Edges-with-GeoPandas-and-Contiguity.ipynb shows how to:
- read a graph from a .json file (using the GerryChain reader)
- print the names of the counties and their populations
- build a MIP model in Gurobi to minimize cut edges
- add the contiguity constraints of Hojny et al. (MPC, 2021)
- read a shapefile with GeoPandas
- draw the districting plan on a map with GeoPandas
D5-Min-Perimeter-with-GeoPandas-and-Contiguity.ipynb shows how to:
- read a graph from a .json file (using the GerryChain reader)
- print the names of the counties and their populations
- build a MIP model in Gurobi to minimize total perimeter length of the districts
- add the contiguity constraints of Hojny et al. (MPC, 2021)
- read a shapefile with GeoPandas
- draw the districting plan on a map with GeoPandas
D6-Min-Moment-of-Inertia.ipynb shows how to:
- read a graph from a .json file (using the GerryChain reader)
- print the names of the counties, their populations, and their lat-long coordinates
- build a MIP model in Gurobi to minimize moment of inertia
- read a shapefile with GeoPandas
- draw the districting plan on a map with GeoPandas
D7-Min-Moment-of-Inertia-with-Contiguity.ipynb shows how to:
- read a graph from a .json file (using the GerryChain reader)
- print the names of the counties, their populations, and their lat-long coordinates
- build a MIP model in Gurobi to minimize moment of inertia
- add the contiguity constraints of Shirabe (2005 and 2009). See Oehrlein and Haunert, 2017 and Validi et al., 2020 for more details.
- read a shapefile with GeoPandas
- draw the districting plan on a map with GeoPandas
Here are some examples of student projects from the Spring 2021 semester of IEM 4013: