Область оптимизации охватывает множество различных областей моделей и алгоритмов. Вы можете классифицировать полевую базу по множеству различных критериев: линейный или нелинейный, выпуклый или невыпуклый, непрерывный или дискретный и т.д. другое, что мне очень интересно. В этой статье мы собираемся глубже погрузиться в разницу между динамическим программированием и целочисленным программированием с помощью интересной и хорошо изученной задачи о рюкзаке.
Что такое проблема с рюкзаком
Проблема ранца, пожалуй, широко известна как одна из задач Leetcode среднего уровня. Но даже до Leetcode, рюкзак был охвачен введением классов целочисленного программирования и, возможно, классов информатики более высокого уровня из-за его рекурсивного характера и легкой постановки задачи. Как специалист по оптимизации, задача о рюкзаке - одна из первых задач, которую вы изучаете в классе целочисленного программирования. Более того, задача о рюкзаке на самом деле является NP-сложной задачей! Однако это одна из трудностей NP, которые мы можем решить довольно эффективно. Это еще одна причина, по которой мы хотим начать с этого!
Напомним, в чем состоит задача о рюкзаке. Предположим, вы собираетесь в путешествие и у вас есть список из n предметов, которые вы хотели бы носить с собой в рюкзаке (или, если хотите, в рюкзаке). У каждого предмета есть вес и оценка полезности. Вы хотите найти подмножество элементов, общий вес которых ниже порогового значения W, а общая оценка полезности которых максимальна.
Из описания проблема кажется достаточно простой. Одно предостережение заключается в том, что каждый элемент может быть выбран или не выбран, но он не может быть выбран наполовину или частично. Это хорошее различие между задачей о рюкзаке 0–1, где каждый предмет является целым, и дробной задачей о ранце, где может быть выбрана дробная часть предмета. В реальной жизни задача о рюкзаке 0–1 может рассматриваться как решение, следует ли выбирать фонарик, в то время как дробная задача может заключаться в рассмотрении того, сколько из 1 галлона воды следует выбрать.
Простая эвристика
Главный компромисс в проблеме рюкзака заключается в том, чтобы получить как можно больше очков полезности при соблюдении ограничения по весу. Естественная идея - рассчитать соотношение полезности / веса для каждого предмета, а затем попытаться подогнать предметы, которые имеют более высокий балл полезности на единицу веса, до тех пор, пока не будет достигнут порог веса. Этот алгоритм является жадным и фактически является решением проблемы дробного ранца. Однако это не гарантирует оптимального решения задачи о ранце 0–1, как демонстрирует следующий встречный пример.
Предположим, что спецификации элементов приведены в следующей таблице:
Пороговое значение веса равно 50. Используя жадную эвристику, мы выберем элементы 1 и 2 с общей полезностью 160 и общим весом 30. Очевидно, что это не оптимальное решение, заключающееся в выборе элементов 2 и 3, где общая полезность равна 220, а общий вес равен точно 50. Понятно, что ранжирование с использованием относительного отношения - это хорошо, но оно не принимает во внимание значение абсолютного веса, и элементы не могут быть выбраны дробным образом.
Фактически, можно использовать эту слабость и создавать экземпляры задачи о рюкзаке, которая делает решение жадной эвристики сколь угодно плохим.
Рассмотрим следующую задачу о рюкзаке с порогом веса X
Решение жадного алгоритма выберет только элемент 1 с общей полезностью 1, а не оптимальное решение выбора элемента 2 с оценкой полезности X-1. Поскольку мы делаем X произвольно большим, жадный алгоритм будет работать сколь угодно плохо по сравнению с оптимальным решением.
Подход динамического программирования
Динамическое программирование основано на идее, что в оптимальном решении данный элемент i либо находится в выбранном подмножестве, либо нет. Это свойство определяет рекурсивный характер алгоритма. Пусть I будет набором элементов, u ᵢ, wᵢ будет полезностью и весом элемента i соответственно, W - порог веса, а рюкзак (I, W) - оптимальное решение задачи о рюкзаке с набором элементов I и порог веса W. Математически рекурсию можно определить как
где I \ {i} представляет собой набор элементов I без элемента i.
- Первый член в операторе max - это случай, когда элемент i не в оптимальном решении, поэтому оптимальное решение совпадает с оптимальное решение задачи о рюкзаке с тем же порогом веса и теми же предметами, кроме предмета i.
- Второй член относится к случаю, когда элемент i находится в оптимальном решении, и для выбора остальных элементов в оптимальном решении требуется решить новую задачу о рюкзаке, где набор элементов - I \ {i}, а порог веса - W-wᵢ.
С помощью этого рекурсивного определения мы можем построить таблицу для отслеживания оптимального решения каждой задачи о рюкзаке, начиная с элементов 0 и порогового значения веса 0 до всех элементов в наборе I и порог веса W. Затем всякий раз, когда мы вычисляем решение для ранца (I \ {i}, W-wᵢ), мы можем просто найти решение в таблице.
Вот реализация алгоритма динамического программирования на Python:
def knapSack(weight_threshold, weight_list, util_list):
"""
A Dynamic Programming algorithm that solves the 0-1 Knapsack problem.
Args:
weight_threshold: Weight threshold
weight_list: List of weights for each item in item set I
util_list: utility score of each item i
Returns:
The optimal utility score of the knapsack problem
"""
n = len(util_list)
lookup_table = [[0 for x in range(weight_threshold+1)]
for x in range(n+1)]
# Build table K[][] in bottom up manner
for i in range(n+1):
for w in range(weight_threshold+1):
if i==0 or w==0:
lookup_table[i][w] = 0
elif weight_list[i-1] <= w:
lookup_table[i][w] = (
max(util_list[i-1]
+ lookup_table[i-1][w-weight_list[i-1]],
lookup_table[i-1][w]))
else:
lookup_table[i][w] = (
lookup_table[i-1][weight_threshold])
return lookup_table[n][weight_threshold]
Обратите внимание, что здесь i обозначает количество элементов, доступных для рассмотрения из набора I. Например, i = 2 означает, что мы можем выбирать только из набора элементов 1 и 2. Поскольку w перебирает все возможные веса, а K [i] [w] представляет оптимальную оценку полезности задачи о рюкзаке с пороговым значением веса j и содержит элементы 1, 2,…, i.
Давайте посмотрим, как работает алгоритм DP со следующей проблемой с порогом веса 5:
Таблица K будет выглядеть, как таблица ниже, когда алгоритм завершится с оптимальным решением:
где оптимальное решение может быть найдено при K [3] [5] = 20 и выбраны элементы 2 и 3.
Целочисленное программирование
Другой подход - подход целочисленного программирования. Целочисленное программирование - это программа математической оптимизации, в которой некоторые или все переменные могут быть целыми числами. Целочисленное программирование является NP-полным, поэтому неудивительно, что задача о рюкзаке, которую можно представить как задачу целочисленного программирования, также является NP-сложной. При использовании подхода целочисленного программирования решения обычно моделируются как дискретные переменные решения, а возможные решения описываются набором ограничений. Полученная модель может быть решена с помощью специального алгоритма целочисленного программирования для получения оптимального решения. В этом случае дискретное решение состоит в том, следует ли выбрать элемент или нет. Мы вводим xᵢ, где элемент i взят из набора I, чтобы представить решение, выбран ли элемент i или нет. Если xᵢ = 1, то выбран элемент i, в противном случае xᵢ = 0 и элемент i не выбран.
Модель целочисленного программирования можно сформулировать следующим образом:
Срок
- целевая функция, которую мы хотим максимизировать. В этом случае цель состоит в том, чтобы максимизировать общую оценку полезности выбранного подмножества элементов.
Неравенство
- это ограничение на рюкзак, которое требует, чтобы общий вес выбранных предметов не превышал W.
Модель представляет собой классическую задачу о рюкзаке, смоделированную в виде целочисленной программы. Для решения указанной выше модели можно использовать любые решатели целочисленного программирования. Хороший вариант - Google ORtools, инструмент с открытым исходным кодом для написания и решения моделей оптимизации.
Ниже приведен код Python, который использует ORtools и решатель целочисленного программирования CBC для моделирования и решения задачи о рюкзаке:
def mip(weight_threshold, weight_list, util_list):
"""
A Integer Programming model that solves the 0-1 Knapsack problem.
Args:
weight_threshold: Weight threshold
weight_list: List of weights for each item in item set I
util_list: utility score of each item i
Returns:
The optimal utility score of the knapsack problem
"""
n = len(weight_list)
# initialize the integer programming model with the open source CBC solver
solver = pywraplp.Solver('simple_mip_program', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
# Declare binary variable x for each item from 1 to n
x_dict = {}
for i in range(n):
x_dict[i] = solver.IntVar(0, 1, f'x_{i}')
# Add constraint on total weight of items selected cannot exceed weight threshold
solver.Add(solver.Sum([weight_list[i]*x_dict[i] for i in range(n)]) <= weight_threshold)
# Maximize total utility score
solver.Maximize(solver.Sum([util_list[i]*x_dict[i] for i in range(n)]))
# Solve!
status = solver.Solve()
# Uncomment the section below to print solution details
# if status == pywraplp.Solver.OPTIMAL:
# print('Solution:')
# print('Objective value =', solver.Objective().Value())
# print('Problem solved in %f milliseconds' % solver.wall_time())
# for i in x_dict:
# print(f'{x_dict[i]} = {x_dict[i].solution_value()}')
return solver.Objective().Value()
Стандартный метод решения целочисленного программирования называется Branch-and-Bound. Это подход разделяй и властвуй, который многократно разделяет пространство решений, пока решение не будет найдено и не будет доказано, что оно оптимальное.
Как следует из названия, ветвление и привязка состоит из двух основных действий:
- Граница: для данного набора решений получить оценку верхней / нижней границы наилучшего решения, которое может быть найдено в наборе решений. Например, можно найти верхнюю оценку для задачи о ранце 0–1, решив соответствующую ей дробную задачу о ранце. Поскольку дробная задача о ранце позволяет выбрать часть предмета, а задача о ранце 0–1 - нет, дробная задача о ранце всегда будет давать равное или лучшее объективное значение, которое можно рассматривать как верхнюю границу цели для ранца 0–1. проблема.
- Ветвь: при вычислении границ набора решений мы находим решения, которые удовлетворяют всем ограничениям задачи, но, тем не менее, неосуществимы, поскольку значения решения не являются целыми числами. В этом случае мы можем перейти к одной из переменных с дробным значением - разделив текущее пространство решений на два: (в случае с двоичной переменной) одно, которое заставляет переменные с дробным значением быть равными 0, а другое принудительно устанавливает переменную с дробным значением, чтобы быть 1. Например, решение дробной задачи о ранце может дать решение, которое занимает 50% от элемента 2. Затем можно перейти к переменной элемента 2, разделив пространство решения, чтобы включить элемент 2 или не включить элемент 2.
Давайте рассмотрим решение примера проблемы, которую мы использовали с динамическим программированием, и, надеюсь, это поможет прояснить ситуацию.
Мы начнем с исходной задачи о рюкзаке (I, W), которая в терминах ветвей и границ называется «главной задачей». Сначала мы решаем релаксацию главной проблемы. В целочисленном программировании ослабление обычно относится к линейному ослаблению, когда вместо требования, чтобы каждая двоичная переменная xᵢ была двоичной, мы ослабляем это ограничение и заставляем каждую xᵢ находиться между [0, 1]. В результате получается линейная программа, отсюда и название «линейная релаксация». Интересно, что в случае задачи о ранце линейная релаксация - это просто дробная задача о ранце. Таким образом, мы можем решить эту проблему с помощью эвристики и получить оптимальное решение. Для более общих расслаблений целочисленных программ требуется решение линейной программы.
Решив расслабление ранца (I, W), мы получаем (x_1, x_2, x_3) = (1, 1, 0.67) и цель 22,67. Это решение дает нам две части информации:
- Глобальная верхняя граница цели 22,67, поскольку пространство решений задачи о ранце 0–1 является подмножеством дробной задачи о ранце, лучшая цель ранца 0–1 не может быть лучше, чем 22,67. На самом деле он не может быть лучше 22, поскольку все коэффициенты в задаче о рюкзаке 0–1 являются целыми числами.
Единственная дробная переменная - x₃, которая идеально подходит для перехода.
Затем мы переходим к переменной x₃, добавляя ограничение, и получаем две подзадачи:
а) рюкзак (I, W) с ограничением x₃ = 0
б) рюкзак (I, W) с ограничением x₃ = 1
где каждая подзадача - это новая задача о рюкзаке, и мы повторяем те же шаги и решаем релаксацию каждой подзадачи.
Для подзадачи a) решение ее релаксации дает решение (x₁, x₂, x₃) = (1, 1, 0) и цель 16. Это допустимое решение, которое можно использовать в качестве нижней границы. Другими словами, теперь мы нашли возможное решение с целью 16, мы ищем только решения, которые имеют лучшую цель, чем 16. От любого другого решения с худшей целью можно отказаться.
Для подзадачи b) решение ее ослабления дает решение (x₁, x₂, x₃) = (1, 0,5, 1) и цель 21. Поскольку подзадача а) уже достигла наилучшего целевого значения 16, глобальная верхняя граница может быть обновлена с 22 до 21, поскольку единственный шанс Поиск лучшего решения находится в области решений подзадачи b), и лучшее, что она может получить, - 21. Но поскольку x₂ теперь дробное, мы продолжаем ветвление на x₂ и формируем задачи b1) и b2).
б1) рюкзак (I, W) с ограничением x₂ = 0, x₃ = 1
б2) рюкзак (I, W) с ограничением x₂ = 1, x₃ = 1
Решая подзадачу b1), получаем решение (x₁, x₂, x₃) = (1, 0, 1) с целью 16. Мы можем безопасно отказаться от этой ветки, так как лучшая цель, которую она может достичь - 16, которая уже найдена в подзадаче a). В этом случае, поскольку решение также является интегральным, мы все равно остановимся, поскольку не осталось других решений для исследования проблемы b1), которые потенциально могут дать лучшую цель.
Решая подзадачу b2), получаем (x₁, x₂, x₃) = (0, 1, 1) с целью 20. Поскольку решение является целым и больше, чем предыдущая нижняя граница 16, это новая нижняя граница. И поскольку это последняя ветвь, которую нам нужно изучить, мы можем утверждать, что это оптимальное решение исходной проблемы. Другой сертификат, который показывает оптимальность решения, заключается в том, что глобальная верхняя граница составляет 21, и не существует комбинации элементов, которая дала бы общую оценку полезности 21, таким образом решение задачи 20 является оптимальным.
Ниже приведена блок-схема, на которой резюмируются указанные выше шаги:
Сравнения
Вернемся к обоим подходам. В обоих подходах используется какая-то рекурсивная схема: динамическое программирование использует структуру проблемы и рекурсивно строит в направлении оптимального решения от более мелких проблем, в то время как целочисленное программирование рекурсивно разделяет проблемное пространство на более мелкие стволы и использует оценочные границы, чтобы отбросить неинтересные разделы решения для ускорения Поиск. Динамическое программирование похоже на сверхразумное перечисление, и оно позволяет избежать ненужных вычислений, всегда опираясь на оптимальные решения более простых задач. Целочисленное программирование не обязательно работает исключительно в рамках набора решений. Скорее, он использует информацию, полученную в результате решения ослаблений, для уточнения нижней и верхней границ и работает над сокращением разрыва между границами. Границы могут помочь исключить те части пространства решений, которые не содержат лучших решений, поэтому ветвление и граница могут быть очень эффективными. Динамическое программирование прекрасно, когда проблемная структура хороша, а набор решений умеренный. Целочисленное программирование может быть очень эффективным, если у вас есть эффективные способы вычисления нижних и верхних границ качества решений.
Что лучше для задачи о рюкзаке?
В конце концов, какой из них мы должны использовать для задачи о рюкзаке? Чтобы ответить на этот вопрос, мы проводим две серии экспериментов:
- Запустите оба алгоритма для различных размеров случайно сгенерированных задач о рюкзаке, чтобы увидеть влияние размера на производительность.
- Запустите оба алгоритма на случайно сгенерированных задачах о рюкзаке с различной плотностью ограничений ранца, чтобы увидеть влияние плотности ограничения на производительность.
Влияние размера проблемы на производительность
Размер проблемы является обычным фактором, который следует учитывать, поскольку для решения более крупных проблем обычно требуется больше времени. Мы генерируем экземпляры задачи о рюкзаке с количеством элементов от 100 до 1000. Вес и оценка полезности - это случайно сгенерированные целые числа от 0 до 100. Пороговое значение веса - фиксированное число, равное 100. Мы запускаем оба алгоритма на каждом экземпляре 7 раз, и запишите среднее время решения в секундах. Результаты можно обобщить на следующем графике:
Из приведенного выше графика можно заметить, что для задач небольшого и среднего размера подход динамического программирования очень конкурентоспособен по сравнению с подходом целочисленного программирования. По мере увеличения размера проблемы время решения обоих алгоритмов увеличивается. При такой постановке эксперимента кажется, что нет явного преимущества одного алгоритма перед другим.
Влияние герметичности ранца на производительность
Еще один фактор, на который мы обращаем внимание, - это жесткость ограничения на рюкзак. Жесткое ограничение означает, что большинство элементов не будет выбрано, а слабое ограничение означает, что в конечном итоге будет выбрано большинство элементов. Это напрямую влияет на размер таблицы поиска для динамического программирования. Мы генерируем случайные экземпляры задач о рюкзаке из 100 элементов, которые имеют случайный вес и оценку полезности в диапазоне от 0 до 100. Мы запускаем каждый алгоритм 7 раз на каждом пороговом значении веса, который находится в диапазоне от 50 до 950, и записываем среднее время решения. в секундах. Результаты можно увидеть в таблице ниже:
Из графика видно, что по мере увеличения порога веса время решения увеличивается при использовании подхода динамического программирования, в то время как целочисленное программирование, похоже, не так сильно влияет. Это связано с тем, что размер таблицы динамического программирования и количество итераций прямо пропорциональны порогу веса, в то время как целочисленное программирование напрямую зависит от количества целочисленных переменных и ограничений, поэтому в этом случае жесткость ограничения не оказывает большого влияния на время решения целочисленного программирования.
Заключение
Из экспериментов мы видим, что для задач о рюкзаке с жесткими ограничениями динамическое программирование может быть хорошим выбором, поскольку его эффективность конкурирует с целочисленным программированием, но не требует настройки модели и вызова внешнего решателя. Плюс динамическое программирование имеет бонус - справочную таблицу, которая содержит оптимальные решения задачи о рюкзаке с разными параметрами.
С другой стороны, подход целочисленного программирования лучше, если размер задачи большой, а ограничение на рюкзак не очень жесткое. На целочисленную программу не так сильно влияет изменение плотности ограничения ранца. У динамического программирования есть недостаток, заключающийся в том, что оно не является инвариантным к масштабу, что означает, что если мы умножим веса и пороговое значение веса на один и тот же коэффициент, время решения также увеличится, поскольку размер таблицы поиска составляет weight threshold * number of items. Кстати, решатели целочисленных программ также имеют в своем арсенале больше оружия для более быстрого поиска приемлемого решения и более эффективного уточнения границ. Одним из примеров является множество решателей, которые имеют встроенную эвристику, которая ищет возможные решения, и встроенные сокращения, которые ужесточают границы.
Надеюсь, это ответит на вопрос, когда мы должны использовать какой подход. Если вы знакомы с подходом к генерации столбцов в области оптимизации, вы знаете, что проблема с рюкзаком часто является подзадачей, которую нам необходимо эффективно решать. В литературе задача о рюкзаке всегда решается с помощью динамического программирования, что всегда меня удивляло. Со всем анализом я думаю, что выбор обусловлен тем фактом, что задача о рюкзаке обычно меньше по размеру и жестко ограничена. Надеюсь, это привлечет больше людей, заинтересованных в оптимизации, и дало хорошее представление о том, как работает каждый алгоритм, чтобы найти оптимальное решение.
Для читателей, интересующихся проблемой рюкзака, в Google ORtools есть больше дискуссий здесь, а также есть отличная книга на ту же тему.
