Задача о квадратичном рюкзаке

Квадратичная задача о рюкзаке (QKP) , впервые представленная в 19 веке. представляет собой расширение задачи о рюкзаке , которое допускает квадратичные члены в целевой функции: дан набор предметов, каждый из которых имеет вес, ценность и дополнительную прибыль, которую можно получить, если выбраны два предмета, определить количество предметов, которые нужно включать в коллекцию, не превышая вместимости рюкзака , чтобы максимизировать общую прибыль. Обычно задачи о квадратичном рюкзаке имеют ограничение на количество копий каждого вида предметов: 0 или 1. Этот особый тип QKP образует задачу о квадратичном рюкзаке 0–1, которая впервые обсуждалась Галло и др. Квадратичная задача о рюкзаке 0-1 представляет собой разновидность задачи о рюкзаке, сочетающую в себе черты задачи о неограниченном рюкзаке, задачи о рюкзаке 0-1 и квадратичной задачи о рюкзаке.

Определение

В частности, квадратичная задача о рюкзаке 0–1 имеет следующий вид:

${\text{maximize }}\left\{\sum _{i=1}^{n}p_{i}x_{i}+\sum _{i=1}^{n}\sum _{j=1,i\neq j}^{n}P_{ij}x_{i}x_{j}:x\in X,x{\text{ binary}}\right\}$

${\text{subject to }}X\equiv \left\{x\in \{0,1\}^{n}:\sum _{i=1}^{n}w_{i}x_{i}\leq W;x_{i}\in \{0,1\}{\text{ for }}i=1,\ldots ,n\right\}.$

Здесь двоичная переменная xi _{показывает ,} включен ли предмет i в рюкзак, $p_{i}$ - прибыль, полученная при выборе пункта i и $P_{ij}$ - это прибыль, полученная, если оба пункта i и j добавить .

Неформально, задача состоит в том, чтобы максимизировать сумму ценностей предметов в рюкзаке так, чтобы сумма весов была меньше или равна вместимости рюкзака.

Приложение

Как и следовало ожидать, QKP имеет широкий спектр приложений, включая телекоммуникации , транспортные сети , информатику и экономику . Фактически, Витцгалл впервые обсудил QKP при выборе мест для спутниковых станций, чтобы максимизировать глобальный трафик с учетом бюджетных ограничений. Аналогичная модель применима и к таким задачам, как определение местоположения аэропортов, железнодорожных станций или грузовых терминалов. Приложения QKP в области информатики стали более распространены после первых дней: компиляторов , проблемы проектирования проблема с щелчком , проект очень крупномасштабной интеграции (СБИС). Кроме того, проблемы ценообразования, по-видимому, являются применением QKP, как описано Johnson et al.

Вычислительная сложность

В общем случае вариант решения задачи о рюкзаке (Можно ли достичь значения не ниже V при ограничении определенной емкости W?) является NP-полным . Таким образом, данное решение может быть проверено за полиномиальное время, в то время как ни один алгоритм не может эффективно определить решение.

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

Как частный вариант задачи о рюкзаке, квадратичная задача о рюкзаке 0–1 также является NP-трудной.

Хотя в литературе не существует эффективного алгоритма, существует псевдополиномиальное время, основанное на динамическом программировании и других эвристических алгоритмах, которые всегда могут генерировать «хорошие» решения.

Решение

Хотя задача о рюкзаке является одной из наиболее часто решаемых задач исследования операций (ИЛИ), существует ограниченное количество эффективных алгоритмов, которые могут решать квадратичные задачи о рюкзаке 0–1. Доступные алгоритмы включают, помимо прочего, грубую силу , линеаризацию , и выпуклая переформулировка. Как и в случае с другими NP-сложными задачами, обычно этого достаточно, чтобы найти работоспособное решение, даже если оно не обязательно является оптимальным. Эвристические алгоритмы, основанные на жадном алгоритме и динамическом программировании, могут эффективно дать относительно «хорошее» решение задачи QKP 0–1.

Грубая сила

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

// Input://     Profits (stored in array p)//     Quadratic profits (stored in matrix P)//     Weights (stored in array w)//     Number of items (n)//     Knapsack capacity (W)int max = 0for all subset S do    int value, weight = 0    for i from 0 to S.size-1 do:        value = value + p[i]        weight = weight + w[i]            for j from i+1 to S.size-1 do:                 value = value + P[i][j]    if weight <= W then:        if value > max then:                max = value

Учитывая n предметов, их будет не более $2^{n}$ подмножеств, и для каждого набора законных кандидатов время вычисления заработанных значений равно $O(n^{2})$. Таким образом, класс эффективности алгоритма перебора равен $(2^{n}n^{2})=\lambda (2^{n})$, будучи экспоненциальным.

Линеаризация

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

Стандартная линеаризация

Первый — это стандартная стратегия линеаризации, как показано ниже:

LP1: максимизировать

$\sum _{i=1}^{n}p_{i}x_{i}+\sum _{i=1}^{n}\left(\sum _{j=1,i<j}^{n}(P_{ij}+P_{ji})z_{ij}\right).$

при условии

$z_{ij}\leq x_{i}$ для всех $(i,j),i<j$

$z_{ij}\leq x_{j}$ для всех $(i,j),i<j$

$x_{i}+x_{j}-1\leq z_{ij}$ для всех $(i,j),i<j$

$z_{ij}\geq 0$ для всех $(i,j),i<j$

$x\in X,x$ двоичный

В формулировке LP1 мы заменили член x _i x _j непрерывной переменной z _ij . Это переформулирует QKP в задачу о рюкзаке, которую мы затем можем оптимально решить, используя стандартные решатели.

Линеаризация Гловера

Вторая переформулировка, более краткая, называется линеаризацией Гловера. Гловера показана ниже, где Li _i и U _{Формулировка} — нижняя и верхняя границы $\sum _{j=1,i\neq j}^{n}P_{ij}x_{j}$, соответственно:

LP2: максимизировать

$\sum _{i=1}^{n}p_{i}x_{i}+\sum _{i=1}^{n}z_{i}$

при условии

$L_{i}x_{i}\leq z_{i}\leq U_{i}x_{i}$ для $i=1,\ldots ,n$

$\sum _{j=1,i\neq j}^{n}P_{ij}x_{j}-U_{i}(1-x_{i})\leq z_{i}\leq \sum _{j=1,i\neq j}^{n}P_{ij}x_{j}-L_{i}(1-x_{i})$ для $i=1,\ldots ,n$

$x\in X,x$ двоичный

В формулировке LP2 мы заменили выражение $\sum _{j=1,i\neq j}^{n}P_{ij}x_{i}x_{j}$ с непрерывной переменной z _i . Точно так же мы можем использовать стандартные решатели для решения линеаризованной задачи. Обратите внимание, что линеаризация Гловера включает только $n$ вспомогательные переменные с $2n$ ограничения, в то время как стандартная линеаризация требует ${n \choose 2}$ вспомогательные переменные и $3{n \choose 2}$ ограничения для достижения линейности.

Выпуклая квадратичная переформулировка

Обратите внимание, что нелинейные программы сложно решить из-за возможности застрять на локальном максимуме . Однако когда программа выпуклая , любой локальный максимум является глобальным максимумом . Выпуклая программа предназначена для максимизации вогнутой функции или минимизации выпуклой функции на выпуклом множестве . Множество S выпукло, если $\forall u,v\in S$, $\lambda u+(1-\lambda )v\in S$ где $\lambda \in [0,1]$. То есть любая точка между двумя точками множества также должна быть элементом множества. Функция f является вогнутой, если $f[\lambda u+(1-\lambda )v]\leq \lambda f(u)+(1-\lambda )f(v)$. Функция f является выпуклой, если $f[\lambda u+(1-\lambda )v]\geq \lambda f(u)+(1-\lambda )f(v)$. Неформально функция является вогнутой, если отрезок, соединяющий две точки на графике, лежит выше или на графике, а функция является выпуклой, если ниже или на графике. Таким образом, переписав целевую функцию в эквивалентную выпуклую функцию, мы можем переформулировать программу, сделав ее выпуклой, что можно решить с помощью пакетов оптимизации.

Целевую функцию можно записать как $c^{T}x+x^{T}Cx$ используя обозначения линейной алгебры. Нам нужно сделать P положительной полуопределенной матрицей , чтобы переформулировать выпуклую функцию. В этом случае мы модифицируем целевую функцию так, чтобы она была $p^{T}x+x^{T}Px+\sum _{i=1}^{n}\left(\sum _{j=1,j\neq i}^{n}|P_{ij}|\right)(x_{i}^{2}-x_{i})$ применяя результаты линейной алгебры, где P - диагонально-доминантная матрица и, следовательно, положительно полуопределенная. Эту переформулировку можно решить, используя стандартный коммерческий квадратичный пакет смешанных целых чисел.

Жадный эвристический алгоритм

Джордж Данциг предложил жадный алгоритм аппроксимации задачи о неограниченном рюкзаке, который также можно использовать для решения QKP 0-1. Алгоритм состоит из двух фраз: определить исходное решение и улучшить его.

Сначала вычислите для каждого элемента общий целевой вклад, который можно реализовать, выбрав его: $p_{i}+\sum _{i\neq j}^{n}P_{ij}$, и отсортируйте предметы в порядке убывания потенциальной ценности на единицу веса, $(p_{i}+\sum _{i\neq j}^{n}P_{ij})/w_{i}$. Затем отбирайте в рюкзак предметы с максимальным соотношением стоимости и веса до тех пор, пока не останется места для большего, что и образует исходное решение. Начиная с исходного решения, улучшение проводится путем попарного обмена. Для каждого элемента в наборе решений определите элементы, не входящие в набор, замена которых приводит к улучшению цели. Выберите пару с максимальным улучшением и поменяйте местами. Также существует вероятность того, что удаление одного из набора или добавление одного в набор принесет наибольший вклад. Повторяйте до тех пор, пока не перестанет улучшаться замена. Класс сложности этого алгоритма: $O(2^{n})$ поскольку в худшем случае будут идентифицированы все возможные комбинации элементов.

Кваднап

Quadknap — это точный алгоритм ветвей и границ, предложенный Капрара и др. где верхние границы вычисляются с учетом релаксации Лагранжа , которая аппроксимирует сложную проблему более простой задачей и наказывает за нарушение ограничений с использованием множителя Лагранжа для наложения стоимости нарушений. Quadknap освобождает от целочисленного требования при вычислении верхних границ. Субоптимальные множители Лагранжа получены в результате субградиентной оптимизации и обеспечивают удобную переформулировку проблемы. Этот алгоритм весьма эффективен, поскольку множители Лагранжа стабильны и используются подходящие структуры данных для вычисления точной верхней границы линейного ожидаемого времени для числа переменных. Сообщалось, что этот алгоритм генерирует точные решения случаев, содержащих до 400 двоичных переменных , т. е. значительно больше, чем те, которые можно решить другими подходами. Код написан на C и доступен в Интернете.

Эвристика динамического программирования

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

Алгоритм динамического программирования

Для простоты предположим, что все веса неотрицательны. Цель состоит в том, чтобы максимизировать общую ценность с учетом ограничения: общий вес меньше или W. равен Тогда для каждого $w\leq W$, определять $f(m,w)$ — стоимость наиболее выгодной упаковки первых m найденных предметов общим весом w . То есть пусть

$f(m,w)=\max \left\{\sum _{i=1}^{m}p_{i}x_{i}+\sum _{i=1}^{m}\sum _{j=1,i\neq j}^{m}P_{ij}x_{i}x_{j}:\sum _{i=1}^{m}w_{i}=w,1\leq i\leq m\right\}.$

Затем, $f(m,w)$ это решение проблемы. Обратите внимание, что при динамическом программировании решение проблемы возникает из решения ее более мелких подзадач. В данном конкретном случае начните с первого предмета и постарайтесь найти лучшую упаковку, рассмотрев возможность добавления предметов с ожидаемым весом 𝑤. Если вес добавляемого предмета превышает 𝑤 , то $f(m,w)$ то же самое с $f(m-1,w)$. Учитывая, что предмет имеет меньший вес по сравнению с желаемым весом, $f(m,w)$ либо то же самое, что $f(m-1,w)$ если сложение не дает никакого вклада, или то же самое, что и решение для рюкзака меньшей вместимости, в частности, для рюкзака с вместимостью, уменьшенной на вес выбранного предмета плюс стоимость одного правильного предмета, т.е. $f(m-1,w-w_{m})+p_{m}+\sum _{i=1}^{m-1}P_{im}x_{i}$. В заключение мы имеем, что

$f(m,w)={\begin{cases}\max f(m-1,w),f(m-1,w-w_{m})+p_{m}+\sum _{i=1}^{m-1}P_{im}x_{i}&{\text{if }}w_{m}\leq w\\f(m-1,w)&{\text{otherwise}}\end{cases}}$

Примечание о классе эффективности: очевидно, что время работы этого алгоритма $O(Wn^{2})$, основанный на вложенном цикле и вычислении прибыли от новой упаковки. Это не противоречит тому факту, что QKP является NP-трудной, поскольку W не является полиномиальным по длине входных данных.

Пересмотренный алгоритм динамического программирования

Обратите внимание, что предыдущий алгоритм требует $O(Wn^{2})$ место для хранения текущей упаковки предметов для всех m,w , что может оказаться невозможным для решения крупногабаритных задач. Фактически, это можно легко улучшить, убрав индекс m из $f(m,w)$ поскольку все вычисления зависят только от результатов предыдущего этапа.

Переопределить $f(w)$ быть текущим значением наиболее выгодной упаковки, найденной с помощью эвристики. То есть,

$f(w)=\max \left\{\sum _{i=1}^{m}p_{i}x_{i}+\sum _{i=1}^{m}\sum _{j=1,i\neq j}^{m}P_{ij}x_{i}x_{j}:\sum _{i=1}^{m}w_{i}=w,m\leq n\right\}.$

Соответственно, с помощью динамического программирования мы имеем, что

$f(m)={\begin{cases}\max f(w),f(w-w_{m})+p_{m}+\sum _{i=1}^{m-1}P_{im}x_{i}&{\text{if }}w_{m}\leq w,\\f(w)&{\text{otherwise.}}\end{cases}}$

Обратите внимание, что этот пересмотренный алгоритм все еще работает $O(Wn^{2})$ пока только занимаюсь $O(Wn)$ память по сравнению с предыдущим $O(Wn^{2})$.

Сопутствующие темы исследований

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

Еще одна тема литературы — выявление «сложных» проблем. Исследователи, изучающие QKP 0-1, часто проводят вычислительные исследования. чтобы показать превосходство своей стратегии. Подобные исследования также могут проводиться для оценки эффективности различных методов решения. Для QKP 0-1 эти вычислительные исследования часто полагаются на случайно сгенерированные данные, представленные Gallo et al. По сути, каждое вычислительное исследование QKP 0-1 использует данные, которые генерируются случайным образом следующим образом. Веса представляют собой целые числа, взятые из равномерного распределения в интервале [1, 50], а ограничения емкости — это целое число, взятое из равномерного распределения между 50 и суммой весов элементов. Объективные коэффициенты, то есть значения, выбираются случайным образом из [1100]. Было замечено, что создание экземпляров этой формы приводит к проблемам с очень изменчивой и непредсказуемой сложностью. Поэтому вычислительные исследования, представленные в литературе, могут оказаться необоснованными. Таким образом, некоторые исследования направлены на разработку методологии создания примеров QKP 0–1 с предсказуемым и постоянным уровнем сложности.

См. также

• Задача о рюкзаке
• Комбинаторный аукцион
• Комбинаторная оптимизация
• Постоянная проблема с рюкзаком
• Список проблем с рюкзаком
• Проблема с упаковкой

Внешние ссылки

• Коды Дэвида Пизингера для решения различных задач о рюкзаке
• Коды для задачи о квадратичном рюкзаке