Optimizing representation in redistricting: dual bounds for partitioning problems with non-convex objectives
Authors:
- Jamie FravelJFJamie Fravel
- Robert HildebrandRHRobert Hildebrand
- Nicholas GoedertNGNicholas Goedert
- Laurel TravisLTLaurel Travis
- Matthew PiersonMPMatthew Pierson
Open Access
- 30 March 2026
- journal article
- Published by Springer Nature in Mathematical Methods of Operations Research
- Vol. 103 (1-2) , 21-86
Abstract
We investigate optimization models for the purpose of computational redistricting. Our focus is on nonconvex objectives for estimating expected Black Representatives and Political Representation. The objectives are a composition of a ratio of variables and a normal distribution’s cumulative distribution function (or “probit curve"). We extend the work of Validi et al. (2022), which presented a robust implementation of contiguity constraints. By developing mixed integer linear programming models that closely approximate the parent nonlinear model, our approaches yield tight bounds on these optimization problems. We exhibit the effectiveness of these approaches on county-level data.Keywords
All Related Versions
Funding Information
- Air Force Office of Scientific Research (FA9550-21-0107)
- Office of Naval Research (N00014-20-1-2156)
This publication has 29 references indexed in Scilit:
- Convexification techniques for fractional programsMathematical Programming, 2024
- Voting Rights, Markov Chains, and Optimization by Short BurstsMethodology and Computing in Applied Probability, 2023
- Compact mixed-integer programming formulations in quadratic optimizationJournal of Global Optimization, 2022
- Political districting to minimize cut edgesMathematical Programming Computation, 2022
- Rational polyhedral outer-approximations of the second-order coneDiscrete Optimization, 2021
- Gerrymandering in America2016
- Normalized multiparametric disaggregation: an efficient relaxation for mixed-integer bilinear problemsJournal of Global Optimization, 2015
- Using Piecewise Linear Functions for Solving MINLPs2011
- On the number of segments needed in a piecewise linear approximationJournal of Computational and Applied Mathematics, 2010
- Modeling disjunctive constraints with a logarithmic number of binary variables and constraintsMathematical Programming, 2009