Euristica

Un'euristica è una classe di algoritmi che fornisce soluzioni di qualità ragionevole in tempo polinomiale senza garantire l'ottimalità. L'uso sistematico del termine in RO si è diffuso negli anni 1960-1970 dopo *How to Solve It* di Polya (1945) e l'emergere dei problemi NP-Difficili. Le euristiche si dividono in due famiglie principali: (1) euristiche costruttive che costruiscono una soluzione passo dopo passo dal vuoto — esempi: Christofides (1976) per TSP, vicino più prossimo, savings di Clarke-Wright, inserimento goloso di archi nel commesso viaggiatore e regole di priorità LPT/SPT nello scheduling; (2) euristiche di miglioramento che raffinano una soluzione esistente con piccole mosse di vicinato — 2-opt, k-opt e Lin-Kernighan (1973) sono esempi canonici. Le euristiche si valutano su tre assi: qualità della soluzione (gap rispetto a un bound inferiore), tempo di esecuzione e complessità di implementazione. Alcune euristiche appartengono alla classe degli algoritmi di approssimazione con garanzia di prestazione costante dimostrata (es. l'approssimazione 1.5 di Christofides per TSP metrico); altre sono solo empiricamente forti. In pratica le euristiche fungono da warm-start per solver MIP, generatori di bound primali o soluzione produttiva diretta. Silver, Vidal e de Werra (1980) e Reeves (1993) sono riferimenti classici. Le metaeuristiche (#053) formano il quadro ombrello sopra le euristiche.