Упаковка рюкзака неизвестной вместимости

Видеопрезентация

• 2021-12-12 https://youtu.be/XeZTpQWTDUU

Постановка задачи

• https://www.researchgate.net/publication/248382234_Packing_a_Knapsack_of_Unknown_Capacity

Имеется набор из $n$ предметов $\mathcal{I}$.

• Каждый предмет $i \in \mathcal{I}$ обладает неотрицательной стоимостью $v(i)\in \mathbb{Q}_{\geqslant 0}$ и строго положительным размером $l(i)\in \mathbb{Q}_{>0}$.

• Задача — найти подмножество предметов $S$, обладающее наибольшей суммарной стоимостью, помещающееся в рюкзак емкостью $C$:

Особенность задачи упаковки рюкзака неизвестной вместимости (oblivious knapsack problem) — при выборе подмножества предметов $S$ емкость рюкзака $С$ неизвестна. Все предметы рассматриваются по одному разу в некотором порядке, для каждого предмета возможен один из двух исходов:

• Если рассматриваемый предмет помещается в рюкзак, он должен быть положен.

• Если рассматриваемый предмет не помещается в рюкзак, он откладывается.

Порядок рассмотрения предметов может зависеть от того, какие предметы уже были помещены в рюкзак.

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

Если есть метафора лучше → предлагайте свою.

Решение задачи для заданного набора $\mathcal{I}$ — некоторая политика $\mathcal{P}$ выбора предметов, представимая в виде бинарного дерева решений, в вершинах которого стоят предметы, имеющие двух потомков, выбор которых зависит от того, был ли предмет помещен в рюкзак.

Любой путь от корня этого дерева к листьям содержит каждый предмет ровно один раз. $\mathcal{P}(C)\subseteq \mathcal{I}$ — упаковка политики для заданной вместимости $C$.

b_tree.png

Универсальная политика $\Pi$ для набора $\mathcal{I}$ — политика, при которой выбор следующего предмета не зависит от предыдущих исходов.

• Все пути от корня к листьям в дереве решений такой политики совпадают.

• Она может быть задана как фиксированная перестановка предметов $\Pi = (\Pi_1, \Pi_2, \cdots,\Pi_n)$.

Результат упаковки политики сравнивается с оптимальной упаковкой рюкзака заданной вместимости. Политика $\mathcal{P}$ для набора $\mathcal{I}$ называется $\alpha$-устойчивой ($\alpha$-robust) для вместимости $C$, если $$v(Opt(\mathcal{I}, C)) \leqslant \alpha\cdot v(\mathcal{P(C)}),$$

где $v(\cdot)$ — суммарная стоимость всех предметов в упаковке, $Opt(\mathcal{I}, C))$ — оптимальная упаковка рюкзака вместимости $C$ для набора $\mathcal{I}$.

Политика $\mathcal{P}$ $\alpha$-устойчива, если она $\alpha$-устойчива для для любой вместимости. В таком случае $\alpha$ — множитель устойчивости (robustness factor) политики $\mathcal{P}$.

from collections import namedtuple
import numpy as np

from random import randint

Класс для элемента рюкзака, со стоимостью и весом.

Item = namedtuple('Item', ['size', 'value'])

class Item(Item):
    def __repr__(self):
        return "«$%d/%d⚖️»" % (self.value, self.size)

Класс для самого рюкзака, с функциями добавления, очистки, и перегрузки

class Knapsack:
    def __init__(self, capacity):
        self.capacity = capacity
        self.empty()

    def __repr__(self):
        ''' Выводим компактно все параметры рюкзака, не зависящие от длины'''
        return "«${total_value}°{total_size}⚖️/{capacity}⚖️#{leni} → {slice}…»".format(**vars(self), leni = len(self.items), slice=self.items[:10])

    def add_item(self, item):
        if self.total_size + item.size > self.capacity:
            return False
        self.items.append(item)
        self.total_size += item.size
        self.total_value += item.value
        return True

    def empty(self):
        self.total_size = 0
        self.total_value = 0
        self.items = []

    def fill(self, item_list):
        for item in item_list:
            self.add_item(item)

item1 = Item(1, 4)
item2 = Item(3, 1)
knapsack = Knapsack(2)
res = knapsack.add_item(item1)
res = knapsack.add_item(item2)
knapsack

Модифицированный жадный алгоритм

Рассматривается классический жадный алгоритм для задачи упаковки рюкзака с известной вместимостью.

• Сначала отбрасываются предметы, размер которых превосходит емкость рюкзака,

• затем остальные предметы сортируются в порядке уменьшения плотности $d(i) = v(i)/l(i)$.

• В рюкзак кладутся либо первые $j$ предметов в этом порядке, которые помещаются в рюкзак, но $j+1$ уже не помещается,

  • либо, что является модификацией алгоритма, $j+1$ предмет, если его стоимость превосходит суммарную стоимость всех предыдущих предметов.

mgreedy.png

def MGreedy(knapsack, items):
    filtered_items = filter(lambda x: x.size <= knapsack.capacity, items)
    sorted_items = sorted(filtered_items, key=lambda x: - x.value / x.size)
    s = None

    for item in sorted_items:
        item_added = knapsack.add_item(item)
        if not item_added:
            s = item
            break

    if s is not None and s.value > knapsack.total_value:
        knapsack.empty()
        knapsack.add_item(s)

items = (Item(1, 1), Item(1, 4), Item(1, 3), Item(1, 2), Item(4, 20))
knapsack = Knapsack(3)
MGreedy(knapsack, items)
knapsack

items = (Item(1, 1), Item(1, 4), Item(1, 3), Item(1, 2), Item(3, 10))
knapsack = Knapsack(3)
MGreedy(knapsack, items)
knapsack

items = (Item(1, 1), Item(1, 4), Item(1, 3), Item(1, 2))
knapsack = Knapsack(4)
MGreedy(knapsack, items)
knapsack

Устойчивость модифицированного жадного алгоритма

Известное свойство модифицированного жадного алгоритма: для любого набора предметов $\mathcal{I}$ и любой вместимости рюкзака $C$ в задаче упаковки рюкзака с известной вместимостью $$v(Opt(\mathcal{I}, C)) \leqslant 2\cdot v(MGreedy(\mathcal{I}, C))$$ Проверим это свойство в задаче упаковки рюкзака с целочисленными вместимостью рюкзака, размерами и стоимостями предметов.

В этой задаче оптимальное решение можно найти при помощи алгоритма динамического программирования.

def optimal_package_value(knapsack, items):
    assert (type(knapsack.capacity) == int)
    for item in items:
        assert (type(item.size) == int)

    total_sizes = np.zeros((len(items) + 1, knapsack.capacity + 1), dtype=int)

    for k, item in enumerate(items):
        k = k + 1
        for size in range(1, knapsack.capacity + 1):
            if size >= item.size:
                total_sizes[k][size] = max(total_sizes[k - 1][size], total_sizes[k -1][size - item.size] + item.value)
            else:
                total_sizes[k][size] = total_sizes[k - 1][size]

    return total_sizes[len(items)][knapsack.capacity]

Stas: Опциональная задача (не в 2021 году) — ускорить поиск оптимального решения, используя ЦЛП решатель, доступный из Python, например, ortools.

from ortools.algorithms import pywrapknapsack_solver

def optimal_package_value_ortools(knapsack, items):
    solver = pywrapknapsack_solver.KnapsackSolver(
        pywrapknapsack_solver.KnapsackSolver.
        KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, 'KnapsackBoolean')
    
    values = [it.value for it in items]
    weights = [[it.size for it in items]]
    capacities = [knapsack.capacity]
    solver.Init(values, weights, capacities)
    computed_value = solver.Solve()
    return computed_value

Для этого несколько раз генерируем набор предметов и выбираем такой набор, что стоимость решения, найденного жадным алгоритмом отличается от оптимального сильнее всего.

def search_worst_case(capacity, n_items, n_samples, algorithm, ud = False):
    capacity = capacity
    max_item_size = capacity
    max_item_value = capacity
    max_alpha = -1

    for _ in range(n_samples):
        items = []
        for _ in range(n_items):
            size = randint(1, max_item_size)
            value = size if ud else randint(1, max_item_value)
            items.append(Item(size, value))
        knapsack = Knapsack(capacity)
        optimal_value = optimal_package_value(knapsack, items)
        optimal_value_or = optimal_package_value_ortools(knapsack, items)
        assert(optimal_value == optimal_value_or)
        algorithm(knapsack, items)
        alpha = optimal_value / knapsack.total_value
        if max_alpha == -1 or alpha > max_alpha:
            max_alpha = alpha
            worst_items = items

    return worst_items, max_alpha

Stas: Не совсем понятно, зачем искать наихудший набор для жадного среди случайных наборов — его же легко построить конструктивно.

SIZE = 200
N_ITEMS = 5
N_SAMPLES = 100000

worst_items, max_alpha = search_worst_case(SIZE, N_ITEMS, N_SAMPLES, MGreedy, ud=False)
print('Наибольшее отклонение от оптимальной стоимости:', max_alpha)
print('Набор предметов:', worst_items)
knapsack = Knapsack(SIZE)
MGreedy(knapsack, worst_items)
knapsack

Можно заметить, что наибольшее отклонение суммарной стоимости предметов от оптимальной близко, но не превосходит 2.

Универсальная политика в задаче упаковки рюкзака неизвестной вместимости

Алгоритм имитирует поведение модифицированного жадного алгоритма.

• Сначала определяются меняющие предметы (swap items) — предметы, которые при выполнении жадного алгоритма на рюкзаке соответствующим им вместимости выбирались из-за модификации: сумма стоимостей всех предметов, плотность которых превосходит плотность меняющего предмета, меньше стоимости этого предмета.

def swap_items(items):
    sorted_items = sorted(items, key=lambda x: - x.value/x.size)
    sum_value = 0
    swap_items = []
    for item in sorted_items:
        swap_items.append((item, item.value > sum_value))
        sum_value += item.value
    return swap_items

 swap_items([
  Item(size=1, value=3),
  Item(size=1, value=2),
  Item(size=1, value=1),
  Item(size=3, value=6),
        ])

• Также задается строгий порядок между предметами по плотности, причем если плотность предметов совпадает, сравнение производится по индексу (tie-breaking index).

def comp_items(ext_item1, ext_item2):
    bi1, item1 = ext_item1
    bi2, item2 = ext_item2
    if item1.value / item1.size == item2.value / item2.size:
        return bi1 > bi2
    return item1.value / item1.size > item2.value / item2.size

comp_items( (2, Item(2,1)), (1, Item(4,2)) )

comp_items( (1, Item(2,1)), (2, Item(4,2)) )

comp_items( (2, Item(2,1)), (1, Item(3,2)) )

Универсальная политика формируется следующим образом: предметы обходятся в порядке неубывания размера. Если предмет является меняющим, он добавляется в начало политики. Иначе предмет вставляется в политику так, что все предметы до него имеют больший порядок.

universal.png

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

def Universal(items):
    items_swp = swap_items(items)
    sorted_items = sorted(items_swp, key=lambda x: x[0].size)
    packing_policy = []
    total_value = 0
    for breaking_index, (item, swap_item) in enumerate(sorted_items):
        ext_item = (breaking_index, item)
        if swap_item:
            packing_policy.insert(0, ext_item)
        else:
            j = 0
            while (j < len(packing_policy) and 
                   comp_items(packing_policy[j], ext_item)):
                j += 1
            packing_policy.insert(j, ext_item)
        total_value += item.value

    return [item for _, item in packing_policy]

def fill_universal(knapsack, items):
    knapsack.fill(Universal(items))

items = (Item(1, 1), Item(1, 4), Item(1, 3), Item(1, 2), Item(4, 20))
knapsack = Knapsack(3)
fill_universal(knapsack, items)
knapsack

items = (Item(2.5, 1), Item(1, 4), Item(2.5, 3), Item(2.5, 2), Item(3, 10))
knapsack = Knapsack(3)
fill_universal(knapsack, items)
knapsack

items = (Item(1, 1), Item(1, 4), Item(1, 3), Item(1, 2))
knapsack = Knapsack(4)
fill_universal(knapsack, items)
knapsack

Устойчивость алгоритма Universal

Авторы статьи приводят доказательство того, что сформулированный алгоритм построения универсальной политики обладает таким же множителем устойчивости, что и модифицированный жадный алгоритм $-$ 2. Проверим это утверждение схожим образом, что и для жадного алгоритма.

worst_items, max_alpha = search_worst_case(SIZE, N_ITEMS, N_SAMPLES, fill_universal, ud=False)
print('Наибольшее отклонение от оптимальной стоимости:', max_alpha)
print('Набор предметов:', worst_items)
knapsack = Knapsack(SIZE)
fill_universal(knapsack, worst_items)
knapsack

Наибольшее отклонение суммарной стоимости предметов от оптимальной близко, но не превосходит 2.

Универсальная политика при единичной плотности предметов

Если в задаче построения универсальной политики для рюкзака неизвестной вместимости все предметы имеют единичную плотность $v(i) = l(i)$, можно построить политику с меньшим коэффициентом устойчивости, равным золотому сечению $\varphi \approx 1,618$.

Алгоритм работает следующим образом: сначала предметы сортируются в порядке возрастания стоимости, причем при равенстве задается строгий порядок по индексу. Далее предметы обходятся в полученном порядке. Каждый предмет вставляется в политику так, что все стоимости всех предметов до него в политике при умножении на $\varphi$ превосходит стоимость этого предмета.

universalud.png

PHI = 1.618034


def comp_items_ud(ext_item1, ext_item2):
    bi1, item1 = ext_item1
    bi2, item2 = ext_item2
    if item1.value == item2.value:
        return bi1 > bi2
    return item1.value > item2.value

def UniversalUD(items):
    for item in items:
        assert (item.value == item.size)

    sorted_items = sorted(items, key=lambda x: x.value)
    packing_policy = []

    for item in sorted_items:
        j = 0
        while (j < len(packing_policy) and 
               item.value < packing_policy[j].value * PHI):
            j += 1
        packing_policy.insert(j, item)

    return packing_policy


def fill_universal_ud(knapsack, items):
    knapsack.fill(UniversalUD(items))

Устойчивость алгоритма UniversalUD

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

worst_items, max_alpha = search_worst_case(SIZE, N_ITEMS, N_SAMPLES, MGreedy, ud=True)
print('Наибольшее отклонение от оптимальной стоимости:', max_alpha)
print('Набор предметов:', worst_items)
knapsack = Knapsack(SIZE)
MGreedy(knapsack, worst_items)
knapsack

worst_items, max_alpha = search_worst_case(SIZE, N_ITEMS, N_SAMPLES, fill_universal, ud=True)
print('Наибольшее отклонение от оптимальной стоимости:', max_alpha)
print('Набор предметов:', worst_items)
knapsack = Knapsack(SIZE)
fill_universal(knapsack, worst_items)
knapsack

Полученные значения близки к 2.

В статье приводится доказательство, что коэффициент устойчивости построенной универсальной политики в задаче с единичными плотностями предметов равен $\varphi \approx 1,618$. Это следует из следующего отношения: $$1 + \frac{1}{\varphi} = \varphi$$

worst_items, max_alpha = search_worst_case(SIZE, N_ITEMS, N_SAMPLES, fill_universal_ud, ud=True)
print('Наибольшее отклонение от оптимальной стоимости:', max_alpha)
print('Набор предметов:', worst_items)
knapsack = Knapsack(SIZE)
fill_universal_ud(knapsack, worst_items)
knapsack

Полученное значение коэффициента устойчивости близко к теоретическому.

Stas:Потенциальная задача — рассмотреть из статьи алгоритм с $O(n \log n)$