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

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

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

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

.

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

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

Пример

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

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

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

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

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

В качестве конкретного примера задачи покрытия множества рассмотрим пример 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 }, { b , c }, { a , c }} показывает разрыв целочисленности 4/3.

Обычно разрыв целочисленности переводится в коэффициент аппроксимации алгоритма аппроксимации. Это связано с тем, что алгоритм аппроксимации полагается на некоторую стратегию округления, которая находит для каждого смягченного решения размера не более целочисленного решения (где RR - коэффициент округления). Если есть экземпляр с разрывом целостности IG , то каждая стратегия округления вернет в этом случае округленное решение не менее размера . Поэтому обязательно . Коэффициент округления RR - это только верхняя граница отношения аппроксимации, поэтому теоретически фактический коэффициент аппроксимации может быть ниже 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 0 представляет собой весь набор переменных исходной задачи. Затем для каждой подзадачи i он выполняет следующие шаги.

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

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

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

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

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

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

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

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

Рекомендации