По условиям задачи коммивояжер должен посетить один и только один раз каждый из n городов и вернуться в исходный пункт. Его маршрут должен иметь минимальную длину среди длин возможных маршрутов. Постановка задачи коммивояжера:

min P = min c_ijx_ij,

при выполнении условий

x_ij = 1; x_ij = 1; x_ij 0; x_ij {0,1},

где P — длина маршрута, C = [c_ij] — матрица расстояний между городами, c_ij- расстояние между городами i и j, X = [x_ij] — матрица, задающая маршрут.

Другими словами, маршрут должен представлять собой гамильтонов цикл в графе городов (иначе замкнутую ломаную без пересечений в вершинах городов).