В математике релаксация (смешанной) целочисленной линейной программы — это проблема, которая возникает при снятии ограничения целочисленности каждой переменной.
Например, в целочисленной программе 0–1 все ограничения имеют вид
Вместо этого релаксация исходной целочисленной программы использует набор линейных ограничений
Результирующая релаксация — это линейная программа , отсюда и название. Этот метод релаксации преобразует NP-трудную задачу оптимизации (целочисленное программирование) в связанную задачу, которая решается за полиномиальное время (линейное программирование); решение расслабленной линейной программы может быть использовано для получения информации о решении исходной целочисленной программы.
Рассмотрим задачу покрытия множеств , релаксацию линейного программирования которой впервые рассмотрел Ловац в 1975 году. [1] В этой задаче в качестве входных данных дается семейство множеств 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.
Релаксация линейного программирования целочисленной программы может быть решена с использованием любого стандартного метода линейного программирования. Если так случится, что в оптимальном решении все переменные имеют целочисленные значения, то это также будет оптимальным решением исходной целочисленной программы. Однако, как правило, это не так, за исключением некоторых особых случаев (например, проблем с полностью унимодулярными матричными спецификациями).
Однако во всех случаях качество решения линейной программы по крайней мере такое же хорошее, как и у целочисленной программы, поскольку любое решение целочисленной программы также будет допустимым решением линейной программы. То есть, в задаче максимизации расслабленная программа имеет значение, большее или равное значению исходной программы, тогда как в задаче минимизации, такой как задача покрытия множества, расслабленная программа имеет значение, меньшее или равное значению исходной программы. Таким образом, релаксация обеспечивает оптимистическую границу решения целочисленной программы.
В примере задачи покрытия множеств, описанной выше, в которой релаксация имеет оптимальное значение решения 3/2, мы можем вывести, что оптимальное значение решения нерелаксированной целочисленной программы по крайней мере столь же велико. Поскольку задача покрытия множеств имеет значения решения, которые являются целыми числами (число множеств, выбранных в подсемействе), оптимальное качество решения должно быть по крайней мере столь же большим, как следующее большее целое число, 2. Таким образом, в этом случае, несмотря на то, что имеет другое значение по сравнению с нерелаксированной задачей, релаксация линейного программирования дает нам точную нижнюю границу качества решения исходной задачи.
Релаксация линейного программирования является стандартным методом проектирования алгоритмов аппроксимации для сложных задач оптимизации. В этом приложении важным понятием является разрыв целостности , максимальное отношение между качеством решения целочисленной программы и ее релаксацией. В случае задачи минимизации, если реальный минимум (минимум целочисленной задачи) равен , а ослабленный минимум (минимум релаксации линейного программирования) равен , то разрыв целостности этого случая равен . В случае задачи максимизации дробь меняет знак на противоположный. Разрыв целостности всегда равен не менее 1. В приведенном выше примере случай F = {{ a , b }, { b , c }, { a , c }} показывает разрыв целостности 4/3.
Обычно разрыв целочисленности переводится в отношение аппроксимации алгоритма аппроксимации. Это происходит потому, что алгоритм аппроксимации опирается на некоторую стратегию округления, которая находит для каждого расслабленного решения размера целочисленное решение размера не более (где RR — это отношение округления). Если есть экземпляр с разрывом целочисленности IG , то каждая стратегия округления вернет для этого экземпляра округленное решение размера не менее . Поэтому обязательно . Отношение округления RR является лишь верхней границей отношения аппроксимации, поэтому в теории фактическое отношение аппроксимации может быть ниже IG , но это может быть трудно доказать. На практике большое IG обычно подразумевает, что отношение аппроксимации в релаксации линейного программирования может быть плохим, и может быть лучше поискать другие схемы аппроксимации для этой задачи.
Для задачи покрытия множеств Ловас доказал, что разрыв целостности для экземпляра с n элементами равен H n , n- му гармоническому числу . Можно превратить релаксацию линейного программирования для этой задачи в приближенное решение исходного нерелаксированного экземпляра покрытия множеств с помощью техники рандомизированного округления . [2] Дано дробное покрытие, в котором каждое множество S i имеет вес w i , случайным образом выбирается значение каждой переменной-индикатора 0–1 x i , равное 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, в которой некоторым переменным присвоены значения 0 или 1, а остальные переменные по-прежнему могут принимать любое значение. В подзадаче i пусть V i обозначает набор оставшихся переменных. Процесс начинается с рассмотрения подзадачи, в которой не было присвоено ни одного значения переменных, и в которой V 0 является всем набором переменных исходной задачи. Затем для каждой подзадачи i он выполняет следующие шаги.
Хотя теоретически доказать ограничения на производительность алгоритмов такого типа сложно, на практике они могут быть весьма эффективны.
Две целочисленные программы 0–1, которые эквивалентны в том смысле, что они имеют одну и ту же целевую функцию и один и тот же набор допустимых решений, могут иметь совершенно разные релаксации линейного программирования: релаксацию линейного программирования можно рассматривать геометрически, как выпуклый многогранник , который включает все допустимые решения и исключает все другие векторы 0–1, и бесконечно много различных многогранников обладают этим свойством. В идеале хотелось бы использовать в качестве релаксации выпуклую оболочку допустимых решений; линейное программирование на этом многограннике автоматически дало бы правильное решение исходной целочисленной программы. Однако, в общем случае, этот многогранник будет иметь экспоненциально много граней и его будет трудно построить. Типичные релаксации, такие как релаксация задачи покрытия множества, обсуждавшаяся ранее, образуют многогранник, который строго содержит выпуклую оболочку и имеет вершины, отличные от векторов 0–1, которые решают нерелаксированную задачу.
Метод секущей плоскости для решения целочисленных программ 0–1, впервые представленный для задачи коммивояжера Данцигом, Фулкерсоном и Джонсоном в 1954 году [5] и обобщенный на другие целочисленные программы Гомори в 1958 году [6], использует эту множественность возможных релаксаций, находя последовательность релаксаций, которые более жестко ограничивают пространство решений, пока в конечном итоге не будет получено целочисленное решение. Этот метод начинается с любой релаксации заданной программы и находит оптимальное решение с помощью решателя линейного программирования. Если решение присваивает целочисленные значения всем переменным, оно также является оптимальным решением нерелаксированной задачи. В противном случае находится дополнительное линейное ограничение (секущая плоскость или разрез ), которое отделяет полученное дробное решение от выпуклой оболочки целочисленных решений, и метод повторяется для этой новой более жестко ограниченной задачи.
Для поиска разрезов, используемых этим методом, необходимы методы, специфичные для конкретной задачи. Особенно желательно найти плоскости разреза, которые образуют грани выпуклой оболочки целочисленных решений, поскольку эти плоскости являются теми, которые наиболее жестко ограничивают пространство решений; всегда существует плоскость разреза такого типа, которая отделяет любое дробное решение от целочисленных решений. Было проведено много исследований методов поиска этих граней для различных типов задач комбинаторной оптимизации в рамках полиэдральной комбинаторики . [7]
Связанный метод ветвления и разрезания объединяет методы плоскости разрезания и ветвления и границы. В любой подзадаче он запускает метод плоскости разрезания до тех пор, пока не будут найдены все плоскости разрезания, а затем разветвляется по одной из оставшихся дробных переменных.
