Les problèmes d'optimisation difficile se caractérisent par une structure complexe de leur espace des configurations.
C'est-à-dire que lorsque nous cherchons à minimiser la fonction « coût », plusieurs minimums locaux apparaissent ce qui rend difficile la recherche de l'optimum (minimum global).
L'Optimisation Combinatoire consiste à trouver la meilleure solution parmi un nombre fini (mais souvent très grand) de choix.
C'est une branche de la « Programmation Mathématique » qui recouvre les méthodes qui servent à déterminer l'optimum d'une fonction sous des contraintes données.