Разбиение/ветвление

Если задача-кандидат (P) не прозондирована, то (P) разбивается на несколько задач таких, что и .

Например, разбиение (P) на может быть получено с помощью фиксирования одной переменной на одном из возможных значений в оптимальном решении (P). Выбор фиксируемой переменной зависит от стратегии разбиения, которая является частью стратегии ветвления. После разбиения полученные подзадачи добавляются в список задач-кандидатов. Каждая подзадача является ограничением задачи (P), т.к. . Следовательно, и .

Комбинаторная релаксация.Задача комбинаторной оптимизации является релаксацией задачикомбинаторной оптимизации , если существует инъекция (взаимно однозначное отображение) , такая, что и для всех . В большинстве случаев , а ‑ тождественное отображение.

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