1 DISTRITACIÓN ELECTORAL y OPTIMIZACIÓN COMBINATORIA David Romero Instituto de Matemáticas - UNAM Cuernavaca, Morelos COLOQUIO INTERNACIONAL DE DISTRITACIÓN ELECTORAL México, D.F., 8-9 noviembre 2012

2  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 ANTECEDENTES

3 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

4 Problema real METODOLOGÍA Ciencia, industria, finanzas, transporte, economía, etc. Modelo matemático Método de resolución Implantación de la solución Polinomiales NP-completos Problemas Optimización Programación lineal, no-lineal, entera, dinámica Redes y grafos Simulación (estocástica, determinista) exacto heurístico Recocido simulado Búsqueda tabú Algoritmos genéticos fuerza bruta otros

5  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 EJEMPLO de APLICACIÓN (INEGI) Determinar Unidades Primarias de Muestreo (UPM)

6 32 Entidades federativas 2443 municipios más de 190 mil localidades rurales 17,288 AGEB rurales 4,028 Localidades urbanas 40,089 AGEB urbanas 1’096,946 manzanas

7 vecindario Calle alondra Av Gina Calle Lirio Av Fermat Calle Amistad grafo de adyacencia de manzanas MODELO. De la geometría a la combinatoria

8 vecindario Calle alondra Av Gina Calle Lirio Av Fermat Calle Amistad grafo de adyacencia de manzanas MODELO. De la geometría a la combinatoria

9 Procesar las AGEB de manera independiente y secuencial En cada AGEB encontrar una partición S = {U 1, …, U m } que minimice la función objetivo Z(S ) y donde cada U k sea conexa Estrategia

10 Función objetivo (caso urbano) A k =área de manzanas en la UPM U k A k =área de manzanas fuera de U k y dentro del círculo mínimo que contiene a U k V k = número de viviendas en U k V = número “ideal” de viviendas m= número de UPMs en la AGEB -

11 No se conoce un método exacto y eficiente Métodos heurísticos Método de resolución Recocido simulado (simulated annealing)

12  Cálculo de centros  Adyacencia entre manzanas mediante Diagrama de Voronoi Triangulación de Delaunay Adyacencia de manzanas

13 Particiones vecinas Considerando las adyacencias dadas por el grafo generamos particiones vecinas S0S0

14 S1S1 Particiones vecinas Considerando las adyacencias dadas por el grafo generamos particiones vecinas

15 S2S2 Particiones vecinas Considerando las adyacencias dadas por el grafo generamos particiones vecinas

16 ...pasar de una partición a una partición vecina… iteraciones z Método de Mejoras Sucesivas

17 Se utiliza el concepto de vecindad Se cambia de una partición a otra vecina de acuerdo con las reglas del “recocido” (algoritmo) (algoritmo) Se tiene un criterio de paro (criterio) (criterio) El método de Recocido Simulado (simulated annealing)

18 IMPLANTACIÓN COMPUTACIONALIMPLANTACIÓN C

19 GRACIAS

20 temperatura inicial   t o factor de enfriamiento  temperatura de congelación t c tamaño del lote 1. Dados 2. Generar una solución inicial S o => Z(S o ) haciendo t = t o (inicio de la temperatura) mientras no haya equilibrio dinámico generar solución S vecina de S o si Z( S ) < Z( S o ) + t entonces reducir la temperatura t =  × t S o = S (acepta nueva solución) Mientras t  t c (no hay congelación) Algoritmo de Recocido Simulado

21 Soluciones aceptadas z = 10 Equilibrio dinámico Recocido Simulado a temperatura fija

22