Задача о покрытии множества (Set Covering Problem, SCP) — классическая и широко распространенная модель дискретной оптимизации. Она возникает каждый раз, когда необходимо выбрать минимальное количество ресурсов для удовлетворения заданного множества потребностей. SCP формирует математический фундамент для колоссальной индустрии составления расписаний экипажей авиакомпаний, оптимизации маршрутов мусоровозов, планирования смен медперсонала и размещения базовых станций сотовой связи.

Метод Ньютона по праву считается одним из самых мощных и быстро сходящихся алгоритмов в арсенале нелинейного математического программирования. В то время как методы градиентного спуска первого порядка анализируют только "наклон" целевой функции, метод Ньютона привлекает информацию о ее "кривизне", используя вторые производные. Это позволяет алгоритму строить точную параболическую аппроксимацию функции и достигать оптимума с квадратичной скоростью сходимости.

В 1984 году математик Нарендра Кармаркар из AT&T Bell Labs опубликовал алгоритм, который потряс мир математического программирования. До этого момента считалось, что полиномиальные алгоритмы (такие как метод эллипсоидов Хачияна) применимы лишь в теории, а на практике безоговорочно властвует симплекс-метод с его потенциально экспоненциальной сложностью. Алгоритм Кармаркара стал первым методом внутренних точек, который доказал свою полиномиальную сложность $O(n^{3.5} L)$ и при этом на задачах огромной размерности превосходил симплекс-метод по скорости вычислений в десятки раз.

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