Cubrir 500 clientescon el costo mínimo posible.
Un problema NP-difícil del paper de Karp resuelto con dos métodos opuestos: Branch & Bound exacto y un Algoritmo Genético. La diferencia: 83 veces más rápido por solo 1.61% de gap.
500 antenas. 500 clientes. 250,000 decisiones binarias.
Cada cliente debe ser cubierto por al menos una antena. Cada antena tiene un costo. El objetivo: activar el subconjunto más barato que cubra a todos.
Es una instancia clásica del Set Cover Problem, uno de los 21 problemas NP-difíciles de Karp. El espacio de búsqueda es de 2^500 ≈ 3.27 × 10^150 subconjuntos posibles; más combinaciones que átomos en el universo observable.
La matriz de cobertura A ∈ {0,1}500×500 tiene una densidad del 9.99%: cada cliente queda en el radio de cobertura de entre 32 y 70 antenas. Los costos oscilan entre $ 2.000 y $ 3.998.
Una sola desigualdad, repetida 500 veces.
El modelo es de los más limpios de la literatura. Una función objetivo lineal, quinientas restricciones de cobertura, y la condición de binariedad sobre las variables de decisión.
Lo simple del enunciado contrasta con su dureza computacional: la integralidad es la que rompe la convexidad y dispara el costo del Branch & Bound.
500 binarias xj
Una por cada antena candidata. Vale 1 si la antena se activa, 0 en caso contrario. El cromosoma del algoritmo genético es exactamente este vector.
500 de cobertura · 500 de binariedad
Cada cliente queda forzado a recibir al menos una antena que lo cubra. La binariedad es la fuente del salto NP-difícil sobre la versión relajada.
LP relajada (cota inferior): $ 27.860 · Gap de integralidad: 79.43%
Diez minutos. Veintidós mil nodos. La mejor solución entera que MATLAB pudo certificar.
MATLAB intlinprog ataca el problema con Branch and Bound. Relaja la integralidad, resuelve el LP, ramifica sobre la variable fraccional más prometedora y poda toda rama cuya cota supere la mejor entera conocida.
Con un presupuesto de 600s el solver exploró 22,632 nodos. No probó optimalidad. Devolvió la mejor solución entera vista.
min cᵀx · s.a. Ax ≥ 1 · x ∈ {0,1}⁵⁰⁰
Una población. Cien y media de soluciones tentativas. Evolución hacia el mínimo.
El método metaheurístico no certifica optimalidad. A cambio explora el espacio combinatorio en segundos, no en minutos. La pregunta no es si llega al óptimo: es qué tan cerca llega y a qué costo.
Cada generación: evaluar fitness, seleccionar padres, cruzar, mutar, reparar, conservar élite, parar si estancamos.
- 01
- 02
- 03
- 04
- 05
- 06
- 07
Inicialización
Población de 150 cromosomas binarios. Cada cromosoma es un subconjunto S de antenas candidatas. Semilla controlada para reproducibilidad.
Evaluación
Función de fitness penalizada. Costo total de S más penalización por clientes no cubiertos. Empuja hacia soluciones factibles.
Selección
Torneo binario. Dos cromosomas al azar, gana el de menor fitness. Mantiene presión selectiva sin colapsar diversidad temprana.
Cruce
Recombinación uniforme con probabilidad alta. Cada gen se hereda del padre A o B con probabilidad equitativa cuando hay cruce.
Mutación
Bit-flip adaptativo. Empieza agresiva para explorar, decae para explotar. Cuida no perturbar al élite cuando el frente ya está pulido.
Elitismo
Las tres mejores soluciones pasan intactas a la siguiente generación. Garantiza monotonía: la mejor fitness nunca empeora generación a generación.
Estancamiento
Si la mejor solución no mejora durante 80 generaciones seguidas, el bucle termina. Ahorra evaluaciones cuando el frente ya está estable.
- Población
- 150
- Generaciones (máx.)
- 500
- Prob. cruce p_c
- 0.9
- Prob. mutación p_m
- 3% → 0.5%
- Elitismo
- 3
- Criterio de parada
- estancamiento 80 gens
- Convergencia (gen)
- 95
- Semilla
- 13
“Mejor semilla. seed 13. Convergió en gen 95.”
La curva cae rápido. Después se queda quieta.
El GA hace la mayor parte del trabajo en las primeras 95 generaciones. Después solo pule. A los 175 estanca y devuelve.
- Convergencia
- 95
- Semilla
- 13
- Tiempo
- 7,23s
- Población
- 150
CAPÍTULO 07 · COMPARACIÓN
Dos métodos. Una respuesta práctica.
La diferencia se ve mejor con baseline-zoom. En escala completa, ambos costos parecen idénticos. La verdad está en el delta.
Costo · baseline-zoom desde $ 49.000
Eje Y truncado para revelar el delta real. No empieza en cero.
Speedup
más rápido
El GA termina en 7,23 s. El PLE necesita 10 minutos completos y aún así no certifica el óptimo.
- CardinalidadPLE 22·GA 23
el GA usa 1 antena extra
- Tiempo600 s·7.23 s
GA es 83× más rápido
- GarantíaIntegerFeasible·sin certificación formal
el PLE acota residual a 0.386 %
Delta de costo
+$807
+1,61 %
Para producción a escala, la elección es obvia. El PLE fija el techo de calidad; el GA decide en segundos.
CAPÍTULO 08 · ROBUSTEZ
Cinco semillas. CV de 0.46%. El GA es estable.
Ejecutamos el mismo GA cinco veces, cambiando solo la semilla aleatoria. Mismo instance, mismos hiperparámetros, distintos puntos de partida en la búsqueda.
Cada corrida es una muestra independiente. El coeficiente de variación mide cuánto varía el resultado frente a la media. Por debajo del 1% se considera muy estable.
Distribución · 5 semillas · gap vs PLE-ILP
Δ best ($50.253) ↔ worst ($50.795) = $542 · 0,55 pp
Media μ
$ 50.443
costo promedio de las 5 corridas
Desviación σ
$230,6
dispersión absoluta
CV
0,46 %
dispersión relativa · σ / μ
vs PLE · 0,386% residual
El coeficiente de variación es 0,46 %. En lenguaje plano: si volvés a correr el GA, la respuesta apenas se mueve.
CAPÍTULO 09 · CIERRE
Honestidad metodológica:
el exacto no es óptimo,
el genético no es perfecto.
Cada uno sirve para algo distinto.
Cuándo usar el PLE · ILP
Cuando puedes esperar y necesitas saber el mejor resultado posible.
- Benchmark de calidad. Fija el techo de lo posible.
- Certificación: el residual del 0.386% mide qué tan cerca estás del óptimo verdadero.
- Validación de heurísticas nuevas antes de pasarlas a producción.
No en producción si hay timeout.
Cuándo usar el GA
Cuando el tiempo manda y un gap del 1 a 2 % es aceptable.
- Producción a escala. Cuando el problema crece y el tiempo de respuesta es la restricción.
- Decisiones rápidas: 7.23 s vs 10 min cambia el flujo operativo.
- Sensibilidad alta a tiempo. Acepta el 1 a 2 % de gap como costo del realismo.
83× más rápido · CV 0.46 %
El mejor algoritmo no existe; existe el algoritmo que resuelve tu restricción más cara.