COLOQUIO INTERNACIONAL DE DISTRITACIÓN ELECTORAL
México, D.F., 8-9 noviembre 2012
DISTRITACIÓN ELECTORAL
y
OPTIMIZACIÓN COMBINATORIA
David Romero
Instituto de Matemáticas - UNAM
Cuernavaca, Morelos
ANTECEDENTES
 Michael Balinski
• Programación entera (optimización combinatoria)
• Matemáticas para las ciencias políticas
 Tesis doctoral sobre Teoría matemática de votos
 IFE
 Aplicaciones de la Optimización Combinatoria
• Ingeniería eléctrica, química, industrial
• Finanzas
• Transporte y distribución
• Logística
• Física
DISTRITACIÓN ELECTORAL
Criterios frecuentemente en conflicto mutuo:
• Representatividad
• Contigüidad
• Compacidad
• Accesibilidad (compacidad temporal)
• Integración territorial de comunidades indígenas
Explosión combinatoria
→ dificultad de obtener escenarios satisfactorios
¿Computadoras? … no bastan
→ modelos y métodos matemáticos
METODOLOGÍA
Problema real
Modelo matemático
Problemas
Polinomiales
NP-completos
Método de resolución
Implantación de la solución
Ciencia, industria, finanzas,
transporte, economía, etc.
Optimización
• Programación lineal, no-lineal,
entera, dinámica
• Redes y grafos
Simulación (estocástica, determinista)
exacto
heurístico
fuerza bruta
otros
Recocido simulado
Búsqueda tabú
Algoritmos genéticos
EJEMPLO de APLICACIÓN (INEGI)
Determinar
Unidades Primarias de Muestreo (UPM)

El problema
• Subdividir las AGEBs en UPMs

Modelación
• Grafo de adyacencia
• Función objetivo

Método de resolución
• Recocido simulado

Implantación computacional
32 Entidades federativas
2443 municipios
17,288 AGEB rurales
4,028 Localidades urbanas
más de 190 mil
localidades rurales
40,089 AGEB urbanas
1’096,946 manzanas
MODELO. De la geometría a la combinatoria
vecindario
grafo
de adyacencia
de manzanas
MODELO. De la geometría a la combinatoria
vecindario
grafo
de adyacencia
de manzanas
Estrategia
• Procesar las AGEB de manera
independiente y secuencial
• En cada AGEB encontrar una partición
S = {U1, …, Um } que minimice la función
objetivo Z(S ) y donde cada Uk sea
conexa
Función objetivo (caso urbano)

m
Z (S )  P
1
1 m
Vk
V
1

2
m
P
1
2 m
k 1

k 1
Vk = número de viviendas en Uk
V = número “ideal” de viviendas
m = número de UPMs en la AGEB
Ak = área de manzanas en la UPM Uk
A-k = área de manzanas fuera de Uk
y dentro del círculo mínimo que
contiene a Uk
Ak
Ak  Ak
Método de resolución
No se conoce un método exacto y eficiente
Métodos heurísticos
Recocido simulado (simulated annealing)
Adyacencia de manzanas
 Cálculo de centros
 Adyacencia entre manzanas mediante
Diagrama de Voronoi
Triangulación de Delaunay
Particiones vecinas
Considerando las adyacencias dadas por el grafo
generamos particiones vecinas
S0
Particiones vecinas
Considerando las adyacencias dadas por el grafo
generamos particiones vecinas
S1
Particiones vecinas
Considerando las adyacencias dadas por el grafo
generamos particiones vecinas
S2
Método de Mejoras Sucesivas
...pasar de una partición a una partición vecina…
z
iteraciones
El método de Recocido Simulado (simulated annealing)
Se utiliza el concepto de vecindad
Se cambia de una partición a otra vecina
de acuerdo con las reglas del “recocido”
(algoritmo)
Se tiene un criterio de paro
(criterio)
IMPLANTACIÓN COMPUTACIONAL
GRACIAS
Algoritmo de Recocido Simulado
1. Dados
temperatura inicial to
factor de enfriamiento 
temperatura de congelación tc
tamaño del lote 
2. Generar una solución inicial So => Z(So )
haciendo t = to (inicio de la temperatura)
Mientras t  tc (no hay congelación)
mientras no haya equilibrio dinámico
generar solución S vecina de So
si Z( S ) < Z( So ) + t entonces
So = S (acepta nueva solución)
reducir la temperatura t = ×t
Recocido Simulado a temperatura fija
z
 = 10
Equilibrio dinámico
Soluciones aceptadas
Descargar

Distritación Electoral y optimización combinatoria