Релаксация линейного программирования

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

Например, в программе с целочисленными значениями 0–1 все ограничения имеют вид

x_{i}\in \{0,1\}

.

Вместо этого при ослаблении исходной целочисленной программы используется набор линейных ограничений.

0\leq x_{i}\leq 1.

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

Пример

Рассмотрим задачу покрытия множеств , релаксация которой методом линейного программирования была впервые рассмотрена Ловасом в 1975 году. ^[1] В этой задаче на вход дается семейство множеств F = { S ₀ , S ₁ , ...}; задача состоит в том, чтобы найти подсемейство с как можно меньшим количеством множеств, имеющее тот же союз , что и F .

Чтобы сформулировать это как целочисленную программу 0–1, сформируйте индикаторную переменную x _i для каждого набора , _Si которая принимает значение 1, когда Si _. принадлежит выбранному подсемейству, и 0, когда оно не принадлежит Тогда допустимое покрытие можно описать присвоением значений индикаторным переменным, удовлетворяющим ограничениям

\textstyle x_{i}\in \{0,1\}

(то есть допускаются только указанные значения индикаторной переменной) и для каждого элемента e _j объединения F ,

\textstyle \sum _{\{i\mid e_{j}\in S_{i}\}}x_{i}\geq 1

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

\textstyle \min \sum _{i}x_{i}.

Релаксация линейного программирования проблемы покрытия множеств описывает дробное покрытие , в котором входным наборам присваиваются веса так, что общий вес наборов, содержащих каждый элемент, равен по крайней мере одному, а общий вес всех наборов минимизирован.

В качестве конкретного примера задачи о покрытии множества рассмотрим случай F = {{ a , b }, { b , c }, { a , c }}. Существует три оптимальных покрытия набора, каждый из которых включает в себя два из трех заданных наборов. Таким образом, оптимальное значение целевой функции соответствующей целочисленной программы 0–1 равно 2 — числу множеств в оптимальных покрытиях. Однако существует дробное решение, в котором каждому набору присвоен вес 1/2 и для которого общее значение целевой функции равно 3/2. Таким образом, в этом примере расслабление линейного программирования имеет значение, отличное от значения неослабленной целочисленной программы 0–1.

Качество решения спокойных и оригинальных программ

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

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

В примере задачи о покрытии множества, описанной выше, в которой релаксация имеет оптимальное значение решения 3/2, мы можем сделать вывод, что оптимальное значение решения нерасслабленной целочисленной программы как минимум столь же велико. Поскольку задача покрытия множеств имеет целочисленные значения решения (количество множеств, выбранных в подсемействе), оптимальное качество решения должно быть не меньше следующего большего целого числа, 2. Таким образом, в этом случае, несмотря на наличие другого Если получить значение неослабленной задачи, то релаксация линейного программирования дает нам точную нижнюю границу качества решения исходной задачи.

Аппроксимация и разрыв целостности

Релаксация линейного программирования — стандартный метод разработки алгоритмов аппроксимации для сложных задач оптимизации. В этом приложении важным понятием является разрыв целочисленности , максимальное соотношение между качеством решения целочисленной программы и ее релаксацией. В случае задачи минимизации, если действительный минимум (минимум целочисленной задачи) равен $M_{\text{int}}$ , а расслабленный минимум (минимум релаксации линейного программирования) равен $M_{\text{frac}}$ , то разрыв целостности этого экземпляра равен $IG={\frac {M_{\text{int}}}{M_{\text{frac}}}}$ . В задаче максимизации дробь переворачивается. Разрыв целостности всегда равен 1. В приведенном выше примере экземпляр F = {{ a , b }, { b , c }, { a , c }} показывает разрыв целостности 4/3.

Обычно разрыв целостности преобразуется в коэффициент аппроксимации алгоритма аппроксимации. Это связано с тем, что алгоритм аппроксимации опирается на некоторую стратегию округления, которая находит для каждого расслабленного решения размера $M_{\text{frac}}$ , целое решение размера не более $RR\cdot M_{\text{frac}}$ (где RR — коэффициент округления). Если существует экземпляр с разрывом целостности IG , то каждая стратегия округления вернет для этого экземпляра округленное решение размера не менее $M_{\text{int}}=IG\cdot M_{\text{frac}}$ . Поэтому обязательно $RR\geq IG$ . Коэффициент округления RR является лишь верхней границей коэффициента аппроксимации, поэтому теоретически фактический коэффициент аппроксимации может быть ниже, чем IG , но это может быть трудно доказать. На практике большой IG обычно означает, что коэффициент аппроксимации при релаксации линейного программирования может быть плохим, и, возможно, лучше поискать другие схемы аппроксимации для этой задачи.

Для задачи покрытия множества Ловас доказал, что разрыв целочисленности для экземпляра с n элементами равен H _n , n- й номеру гармоники . Релаксацию линейного программирования для этой задачи можно превратить в приближенное решение исходного экземпляра покрытия нерасслабленного множества с помощью техники рандомизированного округления . ^[2] Учитывая дробное покрытие, в котором каждое множество имеет _Si вес wi _, случайным образом выберите значение каждой индикаторной переменной x _i 0–1 , равное 1 с вероятностью w _i × (ln n +1), и 0 в противном случае. Тогда любой элемент e _j имеет вероятность остаться непокрытым менее 1/( e × n ), поэтому с постоянной вероятностью все элементы покрыты. Покрытие, созданное этим методом, с высокой вероятностью имеет общий размер (1+o(1))(ln n ) W , где W — полный вес дробного решения. Таким образом, этот метод приводит к алгоритму рандомизированной аппроксимации, который находит покрытие множества в пределах логарифмического коэффициента оптимума. Как показал Янг в 1995 году ^[3] как случайная часть этого алгоритма, так и необходимость построения явного решения релаксации линейного программирования могут быть устранены с помощью метода условных вероятностей , что приводит к детерминированному жадному алгоритму покрытия множества, известному еще Ловасу, который многократно выбирает множество охватывающее максимально возможное количество оставшихся непокрытых элементов. Этот жадный алгоритм аппроксимирует покрытие множества с точностью до того же коэффициента H _n , который Ловас доказал как разрыв целочисленности для покрытия множества. Существуют веские основания с точки зрения теории сложности полагать, что ни один алгоритм аппроксимации с полиномиальным временем не может достичь значительно лучшего коэффициента аппроксимации. ^[4]

Подобные методы рандомизированного округления и алгоритмы дерандомизированной аппроксимации могут использоваться в сочетании с релаксацией линейного программирования для разработки алгоритмов аппроксимации для многих других задач, как описано Рагхаваном, Томпсоном и Янгом.

Ветви и границы для точных решений

Помимо использования в аппроксимации, линейное программирование играет важную роль в алгоритмах ветвей и границ для вычисления истинного оптимального решения сложных задач оптимизации.

Если некоторые переменные в оптимальном решении имеют дробные значения, мы можем запустить процесс типа ветвей и границ , в котором мы рекурсивно решаем подзадачи, в которых значения некоторых дробных переменных фиксированы либо равными нулю, либо единице. На каждом этапе алгоритма этого типа мы рассматриваем подзадачу исходной целочисленной программы 0–1, в которой некоторым переменным присвоены значения: 0 или 1, а остальные переменные по-прежнему могут принимать любое значение. ценить. В подзадаче i пусть V _i обозначает набор оставшихся переменных. Процесс начинается с рассмотрения подзадачи, в которой значения переменных не были присвоены и в которой V ₀ — это весь набор переменных исходной задачи. Затем для каждой подзадачи i он выполняет следующие шаги.

Вычислите оптимальное решение релаксации линейного программирования текущей подзадачи. То есть для каждой переменной x _j в Vi _{должно быть равно 0 или 1, на ослабленное ограничение, согласно которому оно должно} мы заменяем ограничение, согласно которому x _j находиться в интервале [0,1]; однако переменные, которым уже присвоены значения, не ослабляются.
Если смягченное решение текущей подзадачи хуже, чем лучшее целочисленное решение, найденное на данный момент, вернитесь из этой ветви рекурсивного поиска.
Если в расслабленном решении все переменные установлены на 0 или 1, проверьте его на соответствие лучшему целочисленному решению, найденному на данный момент, и сохраните любое из двух решений, которое является лучшим.
В противном случае пусть x _j будет любой переменной, которой в расслабленном решении присвоено дробное значение. Сформируйте две подзадачи: в одной x _j установлено значение 0, а в другой — x _j установлено значение 1; в обеих подзадачах все еще используются существующие присвоения значений некоторым переменным, поэтому набор оставшихся переменных становится V _i \ { x _j }. Рекурсивно выполните поиск обеих подзадач.

Хотя доказать теоретические границы производительности алгоритмов этого типа сложно, на практике они могут быть очень эффективными.

Метод плоскости разреза

Две целочисленные программы 0–1, которые эквивалентны в том смысле, что они имеют одну и ту же целевую функцию и один и тот же набор допустимых решений, могут иметь совершенно разные релаксации линейного программирования: релаксацию линейного программирования можно рассматривать геометрически как выпуклый многогранник , включающий все допустимые решения и исключает все остальные векторы 0–1, и этим свойством обладает бесконечное множество различных многогранников. В идеале в качестве релаксации хотелось бы использовать выпуклую оболочку возможных решений; линейное программирование на этом многограннике автоматически даст правильное решение исходной целочисленной программы. Однако в целом этот многогранник будет иметь экспоненциально много граней , и его будет сложно построить. Типичные релаксации, такие как релаксация проблемы покрытия множеств, обсуждавшаяся ранее, образуют многогранник, который строго содержит выпуклую оболочку и имеет вершины, отличные от векторов 0–1, которые решают нерелаксированную проблему.

Метод секущей плоскости для решения целочисленных программ 0–1, впервые представленный для задачи коммивояжера Данцигом, Фулкерсоном и Джонсоном в 1954 году. ^[5] и обобщен на другие целочисленные программы Гомори в 1958 году: ^[6] использует преимущества этой множественности возможных релаксаций, находя последовательность релаксаций, которые более жестко ограничивают пространство решений, пока в конечном итоге не будет получено целочисленное решение. Этот метод начинается с любого ослабления заданной программы и находит оптимальное решение с помощью решателя линейного программирования. Если решение присваивает целочисленные значения всем переменным, это также является оптимальным решением неослабленной задачи. В противном случае обнаруживается дополнительное линейное ограничение ( секущая плоскость или разрез ), которое отделяет полученное дробное решение от выпуклой оболочки целочисленных решений, и метод повторяется для этой новой задачи с более жесткими ограничениями.

Для нахождения разрезов, используемых этим методом, необходимы специфичные для задачи методы. Особенно желательно найти секущие плоскости, которые образуют грани выпуклой оболочки целочисленных решений, поскольку именно эти плоскости наиболее сильно ограничивают пространство решений; всегда существует секущая плоскость этого типа, отделяющая любое дробное решение от целочисленного решения. Было проведено много исследований методов поиска этих граней для различных типов задач комбинаторной оптимизации в рамках полиэдральной комбинаторики . ^[7]

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

См. также

Дробная раскраска с помощью линейного программирования — упрощение раскраски графов .
Рандомизированное округление , для получения решения исходной задачи из решения релаксации.

Ссылки

Аардал, Карен ; Вейсмантель, Роберт (1997), «Многогранная комбинаторика: аннотированная библиография», Аннотированная библиография по комбинаторной оптимизации (PDF) , Wiley .
Агмон, Шмуэль (1954), «Метод релаксации для линейных неравенств» , Canadian Journal of Mathematics , 6 : 382–392, doi : 10.4153/CJM-1954-037-2 .
Данциг, Джордж ; Фулкерсон, Др. ; Джонсон, Сельмер (1954), «Решение крупномасштабной проблемы коммивояжера», Журнал Американского общества исследования операций , 2 (4): 393–410, doi : 10.1287/opre.2.4.393 .
Файги, Уриэль (1998), «Порог ln n для аппроксимации покрытия множества», Journal of the ACM , 45 (4): 634–652, CiteSeerX 10.1.1.70.5014 , doi : 10.1145/285055.285059 .
Гомори, Ральф Э. (1958), «Описание алгоритма целочисленного решения линейных программ», Бюллетень Американского математического общества , 64 (5): 275–279, doi : 10.1090/S0002-9904-1958-10224- 4 .
Ловас, Ласло (1975), «О соотношении оптимальных целых и дробных покрытий», Discrete Mathematics , 13 (4): 383–390, doi : 10.1016/0012-365X(75)90058-8 .
Моцкин, Т.С. ; Шенберг, И.Дж. (1954), «Метод релаксации для линейных неравенств» , Canadian Journal of Mathematics , 6 : 393–404, doi : 10.4153/CJM-1954-038-x .
Рагхаван, Прабхакар; Томпсон, Кларк Д. (1987), «Рандомизированное округление: метод доказуемо хороших алгоритмов и алгоритмических доказательств», Combinatorica , 7 (4): 365–374, doi : 10.1007/BF02579324 .
Янг, Нил Э. (1995), «Рандомизированное округление без решения линейной программы», Proc. 6-й симпозиум ACM-SIAM. Дискретные алгоритмы (SODA) , Soda '95, стр. 170–178, ISBN 9780898713497 .

[1] Всадник (1975)

[2] ( Рагхаван и Томпсон, 1987 )

[3] Янг (1995)

[4] ( Файги 1998 )

[5] Данциг, Фулкерсон и Джонсон (1954)

[6] Гомори (1958)

[7] ( Аардал и Вейсмантель, 1997 )

[1]

[2]

[3]

[4]

[5]

[6]

[7]