Почему важна дополнительная расслабленность?

10

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

Две основные причины применения CS (как преподается в аспирантуре и учебниках):

  1. Для проверки оптимальности ЛП
  2. Чтобы помочь решить двойную

Учитывая сегодняшнюю вычислительную мощность и полиномиальные алгоритмы для решения LP, CS по-прежнему актуален с прагматической точки зрения? Мы всегда могли бы решить двойственные проблемы и рассмотреть оба пункта выше. Я согласен, что «более эффективно» решать дуал с помощью CS, но так ли это? Или в CS есть нечто большее, чем кажется на первый взгляд? Где именно CS полезен помимо двух вышеуказанных пунктов ? Я часто видел тексты, ссылающиеся на концепцию CS, когда речь идет об алгоритмах аппроксимации, но я не понимаю его роль там.

кандидат наук
источник
2
Не моя область знаний, но звучит так, как будто вы спрашиваете, почему мы учим свойствам X, хотя решить X очень легко в вычислительном отношении. Например, почему мы учим характеризации двудольности «нет нечетных циклов = двудольных», даже если у нас есть алгоритмы полиномиального времени для проверки двудольности. Это то, что вы спрашиваете, в некотором смысле?
Робин Котари
Не совсем. Я понимаю, "почему" ты этому учишь. Я хотел бы узнать из практического POV, как это используется при решении LP и / или разработке алгоритмов аппроксимации. Что мы понимаем, кроме математических отношений между переменными и ограничениями.
PhD
Ну, я думаю, что это может помочь с получением "аналитических" решений ... которые могут быть более трудными для получения с компьютером.
Усул
1
Я не понимаю вопрос. Только потому, что мы используем калькуляторы и компьютеры для сложения и умножения чисел, нам все еще нужно знать свойства чисел?
Чандра Чекури
@ChandraChekuri - я не это имел в виду. Я просто пытаюсь понять, что же такого хорошего в этой теореме и что делает ее важной. Я не хочу принимать это как «так оно и есть», но хотел бы иметь более глубокое понимание его важности для дуальности LP
PhD

Ответы:

14

Дополнительное расслабление является ключевым моментом при разработке алгоритмов первичного двойственного типа. Основная идея:

  1. Начните с возможного двойного решения .y
  2. Попытка найти первичный выполнимый такой, что удовлетворяет дополнительному расслаблению.x(x,y)
  3. Если шаг 2. успешный, мы сделали. В противном случае препятствие для нахождения дает возможность изменить так, чтобы значение двойной целевой функции увеличивалось. Повторение.xy

Классическим примером является венгерский алгоритм. Алгоритм Форда-Фулкерсона можно рассматривать как еще один пример. Обратите внимание, что шаг 2. является проблемой выполнимости, которая часто проще, чем исходная проблема оптимизации, и также часто может быть решена комбинаторно. Это сила дополнительной расслабленности. Например, в случае двухстороннего сопоставления с минимальными затратами шаг 2 сводится к проверке, существует ли идеальное сопоставление, используя только острые края. В случае максимального потока - шаг 2 сводится к проверке, разделяют ли насыщенные ребра и .stst

Первично-двойственные алгоритмы хороши по многим причинам. С философской точки зрения, они дают больше понимания, чем общий алгоритм. Они обычно дают сильно полиномиальные алгоритмы времени, тогда как у нас все еще нет сильно полиномиальных LP-решателей. Они часто более практичны, чем универсальные алгоритмы. Это особенно верно, если мы не можем записать LP явно, и наш единственный другой выбор - алгоритм эллипсоида, который имеет место с недвойственным согласованием и алгоритмом Эдмондса.

Primal-dual также является очень полезной основой для алгоритмов аппроксимации, используя расслабленные версии дополнительной слабости. Это было полезно при разработке алгоритмов аппроксимации для NP-сложных задач (см., Например, главу 7 книги Уильямсона-Шмойса ) и при разработке онлайн-алгоритмов с хорошим конкурентным соотношением (см. Книгу Бухбиндера и Наора ). Дело в том, что алгоритм поддерживает решение двойственной релаксации LP сложной задачи и на каждом шаге либо находит целочисленное первичное выполнимое такое что приближенная комплементарная слабость удовлетворяется, либо улучшает двойное решениеyxy, Приближенная дополнительная слабость является условием следующего вида: если то соответствующее двойное ограничение является жестким, а если , то соответствующее первичное ограничение будет жестким, если масштабируется с помощью . Это дает коэффициент приближения . Все это очень хорошо объяснено в двух вышеупомянутых источниках.xi>0yj>0xαα

Сашо Николов
источник