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

(Общая) целочисленная программа и ее LP-релаксация

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

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

{\ Displaystyle х_ {я} \ в \ {0,1 \}}

.

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

{\ displaystyle 0 \ leq x_ {i} \ leq 1.}

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

Пример [ править ]

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

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

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

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

{\ displaystyle \ textstyle \ sum _ {\ {я \ 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.

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

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

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

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

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

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

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

Для задачи о покрытии множества Ловас доказал, что пробелом целостности для случая с n элементами является H _n , номер n- й гармоники . Можно превратить релаксацию линейного программирования для этой проблемы в приближенное решение исходного нерелаксированного экземпляра покрытия множества с помощью техники рандомизированного округления ( Raghavan & Tompson 1987 ) . Учитывая дробное покрытие, в котором каждое множество S _i имеет вес w _i , случайным образом выбираем значение каждой индикаторной переменной x _i 0–1 равным 1 с вероятностью w _i × (ln n +1) и 0 в противном случае. Тогда любой элемент e _j с вероятностью меньше 1 / ( e × n ) останется непокрытым, поэтому с постоянной вероятностью все элементы будут покрыты. Покрытие, созданное с помощью этого метода, с высокой вероятностью имеет общий размер (1 + o (1)) (ln n ) W , где W - общий вес дробного раствора. Таким образом, этот метод приводит к алгоритму рандомизированной аппроксимации, который находит заданное покрытие в пределах логарифмического коэффициента оптимума. Как показал Янг (1995) , как случайная часть этого алгоритма, так и необходимость построения явного решения релаксации линейного программирования могут быть устранены с помощьюметод условных вероятностей , приводящий к детерминированному жадному алгоритму для покрытия множества, известному уже Ловасу, который многократно выбирает множество, которое покрывает максимально возможное количество оставшихся непокрытых элементов. Этот жадный алгоритм аппроксимирует покрытие множества с точностью до того же фактора H _n, который Ловас доказал как разрыв целостности для покрытия множества. Существуют веские теоретические причины сложности полагать, что никакой алгоритм полиномиального приближения не может достичь значительно лучшего отношения приближения ( Feige 1998 ).

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

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

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

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

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

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

Метод секущей плоскости [ править ]

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

Алгоритм Гомори для решения целочисленных программ 0-1, первый введенных для задачи коммивояжера по Данциг, Фулкерсон & Johnson (1954) и обобщается на другие целых программы по Гомори (1958) , использует эту множественность возможных релаксаций по поиск последовательности релаксаций, которые более жестко ограничивают пространство решений, пока в конечном итоге не будет получено целочисленное решение. Этот метод начинается с любого ослабления данной программы и находит оптимальное решение с помощью решателя линейного программирования. Если решение присваивает всем переменным целочисленные значения, это также является оптимальным решением нерелаксированной проблемы. В противном случае дополнительная линейная зависимость ( секущая плоскость илиcut ), который отделяет полученное дробное решение от выпуклой оболочки целочисленных решений, и метод повторяется для этой новой задачи с более жесткими ограничениями.

Чтобы найти разрезы, используемые этим методом, нужны специальные методы. Особенно желательно найти плоскости сечения, которые образуют грани выпуклой оболочки целочисленных решений, поскольку именно эти плоскости наиболее сильно ограничивают пространство решений; всегда существует секущая плоскость этого типа, которая отделяет любое дробное решение от целочисленных. Было проведено много исследований методов нахождения этих граней для различных типов задач комбинаторной оптимизации в рамках полиэдральной комбинаторики ( Aardal & Weismantel 1997 ).

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

См. Также [ править ]

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

Ссылки [ править ]

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