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

Генерал) целочисленная программа и его ЛП-релаксация

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

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

{displaystyle x_ {i} в {0,1}}

.

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

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

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

Пример

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

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

{displaystyle extstyle x_ {i} в {0,1}}

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

{displaystyle extstyle sum _ {{imid e_ {j} in S_ {i}}} x_ {i} geq 1}

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

{displaystyle extstyle min sum _ {i} x_ {i}.}

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

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

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

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

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

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

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

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

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

Для задачи о покрытии множеств Ловас доказал, что разрыв целостности для случая с п элементы ЧАС_п, то пth номер гармоники. Можно превратить релаксацию линейного программирования для этой задачи в приближенное решение исходного нерелаксированного случая покрытия множества с помощью техники рандомизированное округление (Рагхаван и Томпсон 1987 ). Учитывая дробное покрытие, в котором каждый набор S_я имеет вес ш_я, случайным образом выбираем значение каждой индикаторной переменной 0–1 Икс_я быть 1 с вероятностью ш_я × (lnп +1) и 0 в противном случае. Тогда любой элемент е_j имеет вероятность меньше 1 / (е×п) остаются непокрытыми, поэтому с постоянной вероятностью все элементы покрываются. Покрытие, созданное с помощью этой техники, с высокой вероятностью имеет общий размер (1 + o (1)) (lnп)W, куда W - общий вес фракционного раствора. Таким образом, этот метод приводит к рандомизированный аппроксимационный алгоритм, который находит заданное покрытие в пределах логарифмического коэффициента оптимума. В качестве Молодой (1995) показал, что как случайная часть этого алгоритма, так и необходимость построения явного решения релаксации линейного программирования могут быть устранены с помощью метод условных вероятностей, что приводит к детерминированному жадный алгоритм для набора cover, известного уже Ловасу, который многократно выбирает набор, который покрывает максимально возможное количество оставшихся непокрытых элементов. Этот жадный алгоритм аппроксимирует заданное покрытие с точностью до ЧАС_п фактор, который Ловас доказал как разрыв целостности для покрытия множества. Существуют веские теоретико-сложные причины полагать, что никакой алгоритм аппроксимации за полиномиальное время не может обеспечить значительно лучший коэффициент аппроксимации (Файги 1998 ).

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

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