Le problème du voyageur de commerce (PVC) symétrique consiste à déterminer le cycle le plus court passant exactement une fois par chacun des noeuds d'un graphe non-orienté. Ce problème possède de nombreuses applications pratiques; leur étude a donné lieu à la définition d'une multitude d'extensions du PVC dont certaines ont acquis leur notoriété propre. En recherche opérationnelle, l'étude du PVC symétrique a suscité l'élaboration de plusieurs algorithmes dont les plus efficaces utilisent la programmation linéaire en nombres entiers. Cet article trace l'évolution des méthodes de programmation linéaire en nombres entiers, et en particulier de celles qui utilisent la relaxation de contraintes, pour la résolution du PVC symétrique et de quelques unes de ses extensions.