Метод релаксации Лагранжа вычисляет неоптимальное решение задачи назначения S-D. Метод расслабляет задачу назначения S-D к задаче назначения 2-D с помощью множества лагранжевых умножителей. Задача расслабленного назначения 2-D обычно известна как двойственная задача, которая может быть решена оптимально с помощью алгоритмов, подобных алгоритму Мункреса. Ограничения затем налагаются на двойственное решение путем решения нескольких задач назначения 2-D, чтобы получить возможное решение исходной задачи. Стоимость двойного решения и возможное решение служат более низкими и верхними границами оптимальной стоимости, соответственно. Алгоритм итеративно пытается минимизировать разрыв между двумя и возможными решениями, обычно известными как двойная погрешность. Итерация останавливается, когда двойной промежуток ниже желаемой погрешности или достигнуто максимальное количество итераций.

При использовании алгоритма аукциона assignsd функция использует алгоритм Эвристического Обновления Цены, чтобы обновить множители Лагранжа. При использовании алгоритмов Munkres и JV функция использует алгоритм Accelerated Subgradient Update.

Для матриц затрат с четко определенными решениями, такими как пассивная ассоциация с высокоточными датчиками, зазор решения сходится в пределах 0,05 (5 процентов) приблизительно за 100 итераций.

Поскольку оптимальное решение неизвестно, зазор решения может быть ненулевым, даже когда возвращенное решение оптимально.