TLDR: A new research paper introduces an integer programming-based method that significantly outperforms existing algorithms like ‘short bursts’ in creating redistricting plans with more majority-minority districts. The approach adapts the stochastic hierarchical partitioning algorithm, incorporating a modified integer program (Majority-T PIP), β-reoptimization for compactness, and a local reoptimization algorithm to iteratively improve district plans. Experiments across multiple states and minority groups demonstrate its effectiveness and efficiency in generating fairer electoral maps.
In the complex world of electoral redistricting, ensuring fair representation for all communities, especially minority groups, is a critical challenge. The Voting Rights Act often necessitates the creation of districting plans that include a higher number of majority-minority districts. This is a computationally intensive problem due to the immense number of possible ways to draw district lines across a state.
Historically, two main algorithmic approaches have been used: Markov Chain Monte Carlo (MCMC) methods, such as the ‘Recombination Markov Chain’ (ReCom) and its derivative ‘short bursts’ algorithm, and methods based on integer programming (IP). While ‘short bursts’ has been a state-of-the-art MCMC approach for maximizing majority-minority districts, it often struggles to achieve near-optimal solutions, potentially due to its focus on compactness over the number of majority-minority districts.
A new research paper, titled Optimizing Districting Plans to Maximize Majority-Minority Districts via IPs and Local Search, introduces a novel methodology that significantly outperforms existing techniques like ‘short bursts’. Authored by Daniel Brous and David Shmoys from Cornell University, this work leverages advanced integer programming and local search to generate districting plans with a greater number of majority-minority districts.
The core of their approach builds upon the ‘stochastic hierarchical partitioning algorithm’ (SHP). This algorithm generates a robust set of potential districts by recursively partitioning a region. The new methodology adapts SHP to specifically optimize for majority-minority districts, rather than just general fairness objectives.
Also Read:
- Advancing Fair Resource Allocation on Structured Networks
- PARBALANS: Advancing Mixed-Integer Programming with Parallel Adaptive Search
Key Innovations for Enhanced Optimization
The researchers introduced several key innovations:
-
Majority-T PIP: They modified the standard partitioning integer program (PIP) to create a ‘majority-T PIP’. This new program simultaneously maximizes for compactness of subregions and the number of majority-T (targeted subpopulation) subregions generated. A ‘balance parameter’ (β) allows for adjusting the relative importance of these two competing objectives.
-
β-Reoptimization: To ensure compactness isn’t sacrificed, a bisection-search-like algorithm called β-reoptimization was developed. This process finds the maximum β value that maintains the same number of majority-T districts as when compactness is not prioritized (β=0), thereby improving the compactness of the resulting districts without reducing minority representation.
-
Local Reoptimization: Inspired by the ReCom MCMC algorithm, this iterative process takes any existing plan and attempts to find modifications that increase the number of majority-T districts. Instead of random redraws, it uses the majority-T PIP to repartition connected subsets of districts, accepting only improvements. This method prioritizes regions with a high amount of ‘wasted’ majority-T population, meaning areas where a minority group is large enough to form a majority district but currently does not.
The researchers conducted extensive experiments using 2010 and 2020 Census demographic data for states including Louisiana, Texas, Virginia, and New Mexico. They focused on Black Voting Age Population (BVAP), Hispanic Voting Age Population (HVAP), and People of Color Voting Age Population (POCVAP).
The results consistently showed that their methods either matched or outperformed the ‘short bursts’ algorithm in generating more majority-T districts. For instance, in Louisiana, their algorithm achieved more majority-POCVAP districts than the maximum obtained by ‘short bursts’. Furthermore, their methods often achieved these superior results with shorter run times, indicating greater efficiency.
The β-reoptimization successfully increased the average compactness scores of the plans without negatively impacting the number of majority-T districts. Local reoptimization proved highly effective in further increasing the number of majority-T districts in almost every experiment.
This research demonstrates the powerful application of integer programming and optimization tools in creating fairer and more representative electoral maps. The methodologies developed offer a robust framework for maximizing majority-minority districts, with potential for future work to explore the trade-offs between compactness and minority representation, and to incorporate additional constraints like minimizing county splits.
