Понятие релаксации (комбинаторная релаксация, линейная релаксация, ранцевая релаксация, релаксация Лагранжа).

Релаксация

Для анализа задач-кандидатов (ЗК) (P) используется релаксация (ослабление) (P_R), позволяющая находить верхнюю границу .

Определение. Задача (P_R) называется релаксацией задачи (P), если выполняются следующие условия:

(1) ;

(2) для ;

(3) для из неравенства следует нераенство .

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

Зондирование

Говорят, что задача-кандидат прозондирована, если выполняется одно из следующих условий:

(F1) анализ релаксированной задачи (P_R) показал, что (P) недопустима. Так, из следует, что .

(F2) анализ релаксированной задачи (P_R) показал, что (P) не имеет допустимых решений, лучших, чем текущий рекорд. Если , то .

(F3) анализ релаксированной задачи (P_R) позволил найти оптимальное решение (P). Например, если ‑ оптимальное решение (P_R), которое допустимо в (P), то ‑ оптимальное решение (P).

Если задача-кандидат (P) прозондирована с помощью одного из вышеописанных критериев, то дальнейшее исследование (P) или ее потомков (подзадач) не нужно. Если выполняется (F3) и , то рекорд заменяется на , а заменяется на .