Конфигурация линейной программы

Конфигурационная линейная программа ( configuration-LP ) — это метод линейного программирования, используемый для решения комбинаторной оптимизации задач . Оно было введено в контексте проблемы сокращения запасов . Позже он был применен к упаковке контейнера. и проблемы с планированием работы . В Configuration-LP существует переменная для каждой возможной конфигурации — каждого возможного мультинабора элементов, который может поместиться в одну корзину (эти конфигурации также известны как шаблоны ). Обычно количество конфигураций экспоненциально зависит от размера задачи, но в некоторых случаях можно получить приближенные решения, используя только полиномиальное количество конфигураций.

В мусорной упаковке

Интегральный ЛП

В задаче об упаковке корзин имеется n предметов разного размера. Цель состоит в том, чтобы упаковать предметы в минимальное количество контейнеров, где каждый контейнер может содержать не более B . — Допустимая конфигурация набор размеров с суммой не более B. это

• Пример : предположим, что размеры элементов равны 3,3,3,3,3,4,4,4,4,4 и B =12. Тогда возможные конфигурации: 3333; 333; 33, 334; 3, 34, 344; 4, 44, 444. Если бы у нас было всего три элемента размера 3, то мы не смогли бы использовать конфигурацию 3333.

Обозначим через S множество различных размеров (и их количество). Обозначим через C множество различных конфигураций (и их количество). Для каждого размера s в S и конфигурации c в C обозначим:

• n _s — количество элементов размера s .
• a _{s , c} — количество вхождений размера s в конфигурации c .
• x _c — переменная, обозначающая количество бункеров с конфигурацией c .

Тогда конфигурация LP упаковки в контейнер будет следующей:

${\text{minimize}}~~~\sum _{c\in C}x_{c}~~~{\text{subject to}}$

$\sum _{c\in C}a_{s,c}x_{c}\geq n_{s}$ для всех s в S (- все n _s предметов размера s упакованы ).

$x_{c}\in \{0,\ldots ,n\}$ для всех c в C (всего существует не более n контейнеров, то есть не более n каждой отдельной конфигурации).

Конфигурация LP представляет собой целочисленную линейную программу , поэтому в общем случае она NP-сложна. Более того, даже сама проблема, как правило, очень велика: в ней есть C переменных и S ограничений. Если наименьший размер элемента равен eB (для некоторой дроби e в (0,1)), то в каждом контейнере может находиться до 1/ e элементов, поэтому количество конфигураций C ~ S ^{1/ и} , которое может быть очень большим, если e мало (если e считать константой, то целочисленную ЛП можно решить методом перебора: существует не более S ^1/е конфигураций, и для каждой конфигурации существует не более n возможных значений, поэтому существует не более $n^{S^{1/e}}$ комбинации для проверки. Для каждой комбинации нам необходимо проверить S- ограничения, поэтому время выполнения равно $S\cdot n^{S^{1/e}}$, который является полиномиальным по n, когда S, e постоянны).

Однако этот ILP служит основой для нескольких алгоритмов аппроксимации. Основная идея этих алгоритмов состоит в том, чтобы свести исходный экземпляр к новому экземпляру, в котором S мало, а e велико, поэтому C относительно мало. Тогда ЗЛП можно решить либо полным перебором (если S , C достаточно малы), либо релаксацией ее в дробную ЛП.

Дробный LP

Дробная конфигурация LP упаковки контейнеров. Это релаксация линейного программирования вышеупомянутой ILP. Он заменяет последнее ограничение $x_{c}\in \{0,\ldots ,n\}$ с ограничением $x_{c}\geq 0$. Другими словами, каждую конфигурацию можно использовать дробное количество раз. Релаксацию впервые представили Гилмор и Гомори. и ее часто называют линейной программой Гилмора-Гомори .

• Пример : предположим, что имеется 31 элемент размера 3 и 7 элементов размера 4, а размер ячейки равен 10. Конфигурации: 4, 44, 34, 334, 3, 33, 333. Ограничения: [0,0 ,1,2,1,2,3]* x =31 и [1,2,1,1,0,0,0]* x =7. Оптимальным решением дробного LP является [0,0,0,7,0,0,17/3]. То есть: имеется 7 бункеров конфигурации 334 и 17/3 бункеров конфигурации 333. Обратите внимание, что только две разные конфигурации необходимы.

Вкратце дробный ЛП можно записать так:

${\text{minimize}}~~\mathbf {1} \cdot \mathbf {x} ~~~{\text{s.t.}}~~A\mathbf {x} \geq \mathbf {n} ~~~{\text{and}}~~\mathbf {x} \geq 0$

Где 1 — вектор (1,...,1) размера C , A — S матрица размера на C , в которой каждый столбец представляет одну конфигурацию, а n — вектор ( n ₁ ,..., n _С ).

Решение дробной ЛП

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

Сначала они строят двойственную линейную программу дробного ЛП:

${\text{maximize}}~~\mathbf {n} \cdot \mathbf {y} ~~~{\text{s.t.}}~~A^{T}\mathbf {y} \leq \mathbf {1} ~~~{\text{and}}~~\mathbf {y} \geq 0$.

Он имеет S переменных y ₁ ,..., y _S и ограничения C : для каждой конфигурации c существует ограничение $A^{c}\cdot y\leq 1$, где $A^{c}$ — столбец A, представляющий конфигурацию c . 3Он имеет следующую экономическую интерпретацию. Для каждого размера s мы должны определить неотрицательную цену y _s . Наша прибыль — это общая стоимость всех товаров. Мы хотим максимизировать прибыль n y при условии, что общая цена товаров в каждой конфигурации не превышает 1.

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

В-третьих, они показывают, что при приближенном решении задачи о рюкзаке можно получить приближенное решение двойственной ЛП, а отсюда — приближенное решение первичной ЛП; см. Алгоритмы упаковки контейнеров Кармаркара-Карпа .

В общем, для любого коэффициента допуска h находит базовое допустимое решение со стоимостью не более LOPT(I) + h и работает во времени:

$O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$,

где S — количество разных размеров, n — количество разных предметов, а размер наименьшего предмета — eB . В частности, если e ≥ 1/ n и h = 1, алгоритм находит решение с не более чем LOPT+1 интервалами во времени: $O\left(S^{8}\log {S}\log ^{2}{n}+S^{4}n\log {S}\log {n}\right)$. Рандомизированный вариант этого алгоритма выполняется за ожидаемое время:

$O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$.

Округление дробной ЛП

Кармаркар и Карп далее разработали способ округления дробной ЛП до приближенного решения целой ЛП; см. Алгоритмы упаковки контейнеров Кармаркара-Карпа . Их доказательство показывает, что аддитивная дыра целочисленности этой ЛП находится за O(log ² ( н )). Позже Хоберг и Ротвосс улучшили свой результат и доказали, что разрыв целочисленности находится за O(log( n )). Самая известная нижняя граница разрыва целочисленности — это константа Ω(1). Нахождение точного разрыва целостности является открытой проблемой.

В покрытии бункера

В задаче о покрытии контейнера имеется n предметов разного размера. чтобы упаковать предметы в максимальное количество контейнеров, причем каждый контейнер должен содержать как минимум B. Цель состоит в том , Естественная конфигурация LP для этой проблемы может быть такой:

${\text{maximize}}~~\mathbf {1} \cdot \mathbf {x} ~~~{\text{s.t.}}~~A\mathbf {x} \leq \mathbf {n} ~~~{\text{and}}~~\mathbf {x} \geq 0$

где A представляет собой все конфигурации элементов с суммой не ниже B (можно брать только конфигурации, минимальные по включению). Проблема с этой ЛП заключается в том, что в задаче о покрытии контейнеров обработка мелких предметов проблематична, поскольку мелкие предметы могут быть необходимы для оптимального решения. При разрешении мелких предметов количество конфигураций может оказаться слишком большим даже для техники Кармаркара и Карпа. Чирик, Джонсон и Кеньон представить альтернативный LP. Во-первых, они определяют набор элементов, которые называются small . Пусть T — общий размер всех мелких предметов. Затем они создают матрицу A, представляющую все конфигурации с суммой <2. Затем они рассматривают вышеуказанную ЛП с одним дополнительным ограничением: $${\text{maximize}}~~\mathbf {1} \cdot \mathbf {x} ~~{\text{s.t.}}$$$$A\mathbf {x} \leq \mathbf {n}$$$$\sum _{c\in C:sum(c)<B}(B-sum(c))\cdot x_{c}\leq T$$$$\mathbf {x} \geq 0$$Дополнительное ограничение гарантирует, что «свободное место» в контейнерах может быть заполнено мелкими предметами. Двойной вариант этой ЛП более сложен и не может быть решен с помощью простого оракула разделения рюкзака. Чирик, Джонсон и Кеньон представить другой метод решения этой задачи приблизительно за экспоненциальное время в 1/эпсилон. Янсен и Солис-Оба представить улучшенный метод решения этой задачи приблизительно за экспоненциальное время в 1/эпсилон.

В машинном планировании

В задаче планирования несвязанных машин имеется m разных машин, которые должны обрабатывать n разных заданий. Когда машина i обрабатывает задание j занимает время pi _{, это , j} . Цель состоит в том, чтобы распределить задания между машинами так, чтобы максимальное время завершения работы машины было как можно меньшим. Вариант решения этой проблемы таков: при заданном времени T существует ли раздел, в котором время завершения всех машин не превышает T ?

Для каждой машины i существует конечное число подмножеств заданий, которые могут быть обработаны машиной за время не более T. i Каждое такое подмножество называется конфигурацией машины i . Обозначим через C _i ( T набор всех конфигураций для машины i в данный момент времени T. ) Для каждой машины i и конфигурации c в C _i ( T ) определите переменную $x_{i,c}$ который равен 1, если фактическая конфигурация, используемая на машине i, равна c , и 0 в противном случае. Тогда ограничения LP таковы:

• $\sum _{c\in C_{i}(T)}x_{i,c}=1$ для каждой машины i в 1,..., m;
• $\sum _{i=1}^{m}\sum _{c\ni j,c\in C_{i}(T)}x_{i,c}=1$ для каждого задания j в 1,..., n;
• $x_{i,j}\in \{0,1\}$ для каждого i , j .

Характеристики

Разрыв целостности конфигурации-LP для планирования несвязанных машин равен 2.

См. также

• Упаковка в контейнеры с высокой кратностью