Cubrir 500 clientescon el costo mínimo posible.
Un problema NP-difícil del paper de Karp (1972), resuelto con dos métodos opuestos: Branch & Bound exacto y un Algoritmo Genético. El resultado: 83 veces más rápido a cambio de un costo apenas 1.61 % mayor.
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 encontró antes de agotar el tiempo.
MATLAB intlinprog resuelve el problema con Branch and Bound. Relaja la condición de binariedad, resuelve el LP, ramifica sobre la variable fraccionaria más prometedora y descarta toda rama cuya cota inferior supere a la mejor entera ya encontrada.
Con un presupuesto de 600s el solver exploró 22,632 nodos.
min cᵀx · s.a. Ax ≥ 1 · x ∈ {0,1}⁵⁰⁰
Una población. Ciento cincuenta soluciones candidatas. Evolución hacia el costo mínimo.
El método metaheurístico no garantiza la solución óptima. A cambio, explora el espacio combinatorio en segundos en lugar de 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 inicial de 150 cromosomas binarios. Cada cromosoma representa un subconjunto S de antenas candidatas. La semilla queda fija para que el resultado sea reproducible.
Evaluación
Función de fitness penalizada: costo total de S más una multa por cada cliente sin cubrir. Empuja la búsqueda hacia soluciones factibles.
Selección
Torneo binario. Se enfrentan dos cromosomas al azar y gana el de menor fitness. Mantiene presión para mejorar sin perder diversidad al inicio.
Cruce
Recombinación uniforme con probabilidad 0.9. Cuando ocurre el cruce, cada gen del hijo se hereda del padre A o del padre B con la misma probabilidad.
Mutación
Bit-flip adaptativo. Empieza alta para explorar el espacio y baja para refinar la mejor solución. No se aplica al élite, para no dañar el frente ya pulido.
Elitismo
Las tres mejores soluciones pasan intactas a la siguiente generación, sin cruce ni mutación. Esto garantiza que el mejor costo nunca empeora entre generaciones.
Estancamiento
Si la mejor solución no mejora durante 80 generaciones seguidas, el algoritmo se detiene. Ahorra evaluaciones cuando la búsqueda 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 refina. A los 175 detecta estancamiento y se detiene.
- 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 los 10 minutos completos y aun así no garantiza 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 la brecha 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 se vuelve 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.