Political Districting to Minimize Cut Edges

Python code for the paper "Political districting to minimize cut edges" by Hamidreza Validi and Austin Buchanan.

We consider a stylized redistricting problem.

The input is graph G=(V,E), integer k, population vector p, and bounds L and U.

The task is to find a partition of V into k subsets V_1, V_2, ..., V_k such that:

1. each G[V_i] is connected,
2. each V_i has population within [L,U], and
3. the number of edges between partitions is minimized.

For this problem, we consider multiple mixed integer programming (MIP) formulations. We solve them with the Gurobi solver. The code uses lots of "tricks" to speed up the computations (e.g., strong extended formulation for cut edges objective, symmetry handling techniques, safe variable fixing rules, different approaches for imposing contiguity constraints, heuristic warm start with GerryChain, etc).

Require

To run the code, you will need installations of Gurobi and GerryChain.

The input data is duplicated from Daryl DeFord's website.

The shape files used to draw maps are duplicated from Eugene Lykhovyd's website.

Run

You can run the code from command line, like this:

C:\Cut-Edges\src>python3 main.py config.json 1>>log-file.txt 2>>error-file.txt

config.json

The config file can specify a batch of runs. A particular run might look like this:

• state: OK
• level: county
• base: hess
• fixing: true
• contiguity: scf
• symmetry: default
• extended: true
• order: B_decreasing
• heuristic: true
• lp: true

The config.json file might look like this:

{
  "run1": {"state": "ME", "level": "county", "base": "hess", "fixing": true, "contiguity": "scf", "symmetry": "default", "extended": true, "order": "B_decreasing", "heuristic": false, "lp": true},
  "run2": {"state": "NM", "level": "county", "base": "hess", "fixing": true, "contiguity": "scf", "symmetry": "default", "extended": true, "order": "B_decreasing", "heuristic": true, "lp": true},
  "run3": {"state": "ID", "level": "county", "base": "hess", "fixing": true, "contiguity": "scf", "symmetry": "default", "extended": true, "order": "B_decreasing", "heuristic": true, "lp": true},
  "run4": {"state": "WV", "level": "county", "base": "hess", "fixing": true, "contiguity": "scf", "symmetry": "default", "extended": true, "order": "B_decreasing", "heuristic": true, "lp": true},
  "run5": {"state": "LA", "level": "county", "base": "hess", "fixing": true, "contiguity": "scf", "symmetry": "default", "extended": true, "order": "B_decreasing", "heuristic": false, "lp": true},
  "run6": {"state": "AL", "level": "county", "base": "hess", "fixing": true, "contiguity": "scf", "symmetry": "default", "extended": true, "order": "B_decreasing", "heuristic": true, "lp": true},
  "run7": {"state": "AR", "level": "county", "base": "hess", "fixing": true, "contiguity": "scf", "symmetry": "default", "extended": true, "order": "B_decreasing", "heuristic": true, "lp": true},
  "run8": {"state": "OK", "level": "county", "base": "hess", "fixing": true, "contiguity": "scf", "symmetry": "default", "extended": true, "order": "B_decreasing", "heuristic": true, "lp": true},
  "run9": {"state": "MS", "level": "county", "base": "hess", "fixing": true, "contiguity": "scf", "symmetry": "default", "extended": true, "order": "B_decreasing", "heuristic": true, "lp": true},
  "run10": {"state": "NE", "level": "county", "base": "hess", "fixing": true, "contiguity": "scf", "symmetry": "default", "extended": true, "order": "B_decreasing", "heuristic": true, "lp": true},
  "run11": {"state": "IA", "level": "county", "base": "hess", "fixing": true, "contiguity": "scf", "symmetry": "default", "extended": true, "order": "B_decreasing", "heuristic": true, "lp": true},
  "run12": {"state": "KS", "level": "county", "base": "hess", "fixing": true, "contiguity": "scf", "symmetry": "default", "extended": true, "order": "B_decreasing", "heuristic": true, "lp": true}
}

Config options

Generally, each run should pick from the following options:

• state : {AL, AK, AZ, AR, CA, ... }
  • See list of 2-letter codes
• level : {county, tract}
  • Either treat counties or census tracts as indivisible land units
• base : {hess, labeling}
  • Hess model uses binary variables x_ij that equal one when vertex i is assigned to the district rooted at vertex j
  • Labeling model uses binary variables x_ij that equal one when vertex i is assigned to district number j, where j in {1, 2, ..., k }
• fixing : {True, False}
  • If true, will apply procedures to (safely) fix some variables to zero or one
• contiguity : {none, lcut, scf, shir}
  • none means that contiguity is not imposed
  • LCUT imposes contiguity with length-U a,b-separator inequalities (in branch-and-cut fashion)
  • SCF imposes contiguity with a single-commodity flow model. See Hojny et al
  • SHIR imposes contiguity with a multi-commodity flow model. See Shirabe2005 and Shirabe2009 and Oehrlein and Haunert and Validi et al.
• symmetry : {default, aggressive, orbitope}
  • Default uses whatever the Gurobi MIP solver does by default
  • Aggressive is a Gurobi setting that seeks to exploit symmetry
  • Orbitope is the extended formulation for partitioning orbitopes due to Faenza and Kaibel
• extended : {True, False}
  • If true, use an extended formluation to better capture the cut edges objective function. See Ferreira et al
• order : {none, decreasing, B_decreasing}
  • If none, the given vertex ordering will be used
  • If decreasing, the vertices will be sorted in terms of decreasing population
  • If B_decreasing, a vertex subset B in which all components of G[B] have population less than L will be placed at back, others placed at front by decreasing population
• heuristic : {True, False}
  • If true, will use a heuristic MIP warm start obtained from GerryChain
• lp : {True, False}
  • If true, will create a (separate) model for the LP relaxation and solve it to evaluate LP strength