  The American winner-take-all congressional district system empowers
politicians to engineer electoral outcomes by manipulating district boundaries.
Existing computational solutions mostly focus on drawing unbiased maps by
ignoring political and demographic input, and instead simply optimize for
compactness. We claim that this is a flawed approach because compactness and
fairness are orthogonal qualities, and introduce a scalable two-stage method to
explicitly optimize for arbitrary piecewise-linear definitions of fairness. The
first stage is a randomized divide-and-conquer column generation heuristic
which produces an exponential number of distinct district plans by exploiting
the compositional structure of graph partitioning problems. This district
ensemble forms the input to a master selection problem to choose the districts
to include in the final plan. Our decoupled design allows for unprecedented
flexibility in defining fairness-aligned objective functions. The pipeline is
arbitrarily parallelizable, is flexible to support additional redistricting
constraints, and can be applied to a wide array of other regionalization
problems. In the largest ever ensemble study of congressional districts, we use
our method to understand the range of possible expected outcomes and the
implications of this range on potential definitions of fairness.
