Master's Thesis
Logic-based algorithms for political districting
— 2023
Key information
Authors:
Supervisors:
Published in
November 13, 2023
Abstract
A divisão de distritos para as eleições tem sido motivo de controvérsia desde há muito tempo devido às tentativas de alguns partidos políticos redesenharem os distritos eleitorais para obterem uma vantagem nas eleições sobre os seus adversários. Isto é conhecido como gerrymandering e há muito que constitui um desafio. Desde os anos 60, foram propostas várias abordagens para resolver este problema, criando mapas eleitorais que visam maximizar o quão compactos os distritos são, evitando assim situações de gerrymandering. No entanto, este problema é computacionalmente complexo e a criação de mapas eleitorais deve satisfazer múltiplos critérios, o que representa um desafio significativo. Neste trabalho, é apresentada uma nova abordagem ao problema da divisão dos distritos. Reconhecendo os desafios colocados por extensas restrições de contiguidade, é proposta uma adição incremental destas restrições, em oposição à sua incorporação simultânea, com o objetivo de aliviar a carga computacional do solver. Além disso, foi concebida uma gama de restrições de otimização para facilitar a tarefa do solver. Por fim, foi desenvolvido um modelo de Programação Linear Inteira, dando prioridade à minimização das diferenças populacionais em vez de maximizar o quão compacto um distrito é. Os resultados experimentais destacam a eficácia da abordagem incremental em modelos que maximizam o quão compacto um distrito é. No entanto, esta abordagem é insuficiente em modelos que minimização as diferenças de população. Além disso, os resultados dos modelos concebidos para minimizar as diferenças populacionais sublinham a margem existente para melhorias no domínio da Programação Linear Inteira para tais modelos. Political districting has been a cause of controversy for a long time due to the attempts of some political parties to redraw electoral districts in order to gain an advantage in the elections over their opponents. This is known as gerrymandering, and it has long been a challenge in both computer science and political science. Since the 1960s, various approaches have been proposed to address this issue by creating electoral maps that aim to maximize district compactness, thereby preventing gerrymandering. However, this problem is computationally complex, and the creation of electoral maps must satisfy multiple criteria, presenting a significant challenge. In this work, a novel approach to the intricate problem of political districting is introduced. Recognizing the formidable challenges posed by extensive contiguity constraints, an incremental addition of these constraints is proposed, as opposed to their simultaneous incorporation, with the aim of alleviating the computational burden on the solver. Additionally, a range of optimization constraints has been designed to facilitate the solver's task. Furthermore, an Integer Linear Programming (ILP) model has been developed, prioritizing the minimization of population differences opposed to maximizing compactness. The experimental results highlight the effectiveness of the incremental addition of constraints in models focused on maximizing compactness. However, this approach falls notably short in models that prioritize the minimization of population differences. Furthermore, the outcomes from models designed to minimize population differences underscore the existing room for improvement in the realm of Integer Linear Programming for such models.
Publication details
Authors in the community:
João Filipe Boucinha de Sá
ist193844
Supervisors of this institution:
Inês Lynce
ist14029
RENATES TID
203837410
Degree Name
Mestrado em Engenharia Informática e de Computadores
Fields of Science and Technology (FOS)
electrical-engineering-electronic-engineering-information-engineering - Electrical engineering, electronic engineering, information engineering
Keywords
- Integer Linear Programming
- Compactness
- Contiguity
- Political Districting
- Gerrymandering
- Programação Linear Inteira
- Compacidade
- Contiguidade
- Círculos Eleitorais
Publication language (ISO code)
eng - English
Rights type:
Embargo lifted
Date available:
September 16, 2024
Institution name
Instituto Superior Técnico