Heurística

Una heurística es una clase de algoritmos que entrega soluciones de calidad razonable en tiempo polinomial sin garantizar optimalidad. El uso sistemático del término en IO se difundió en los años 1960-1970 tras *How to Solve It* de Polya (1945) y la aparición de los problemas NP-Difíciles. Las heurísticas se agrupan en dos familias principales: (1) heurísticas constructivas que construyen una solución paso a paso desde vacío — ejemplos: Christofides (1976) para TSP, vecino más cercano, ahorros de Clarke-Wright, inserción voraz de aristas en el viajante y reglas de prioridad LPT/SPT en scheduling; (2) heurísticas de mejora que refinan una solución existente mediante pequeños movimientos de vecindario — 2-opt, k-opt y Lin-Kernighan (1973) son ejemplos canónicos. Las heurísticas se evalúan en tres ejes: calidad de la solución (gap respecto a una cota inferior), tiempo de ejecución y complejidad de implementación. Algunas heurísticas pertenecen a la clase de algoritmos de aproximación con garantía constante demostrada (p. ej. la 1.5-aproximación de Christofides para TSP métrico); otras son sólo fuertes empíricamente. En la práctica las heurísticas sirven como entrada de arranque cálido a solvers MIP, generadores de cotas primales o solución directa de producción. Silver, Vidal y de Werra (1980) y Reeves (1993) son referencias clásicas. Las metaheurísticas (#053) forman el marco paraguas sobre las heurísticas.