El problema del agente viajero y de la ruta mínima entre dos ciudades, requiere de un proceso de optimización. Los otros problemas sólo tratan de satisfacer restricciones.
La mayoría de los problemas se pueden plantear tanto como de optimización como de satisfacción de restricciones.
La diferencia entre los dos puede ser muy importante. Encontrar una ruta entre ciudades en el problema del agente viajero es trivial, encontrar la ruta más corta es NP.
Una idea fundamental dentro de los métodos heurísticos es que lo más corto/barato es lo más rápido/mejor.
Si existe un criterio de aceptación (tolerancia) se habla de un problema de semi-optimización. Cuando se habla de alta probabilidad, se tiene un problema de optimización aproximada.
La mayoría de los problemas son de semi-optimización, estableciendo un balance razonable entre calidad de la solución y costo de solución.
Algo un poco más ambicioso es dotar a los algoritmos con parámetros ajustables para cambiar el compromiso entre calidad y costo.