Дизайн задачи оптимизации упаковки / рюкзака

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

Сценарий такой:

  • В мусорные ведра / рюкзаки нужно поместить несколько предметов.
  • У каждого предмета есть два фактора, которые необходимо учитывать при упаковке.
  • У меня есть несколько типов мусорных баков / рюкзаков, которые можно использовать для упаковки
  • Запас урн / ранцев бесконечен.
  • У каждого бункера / рюкзака есть ограничения на каждое из значений из предметов, так что значения предметов складываются кумулятивным образом, но не могут превышать любое ограничение для бункера / рюкзака.
  • У каждого бункера / рюкзака своя стоимость (цена) за его использование.
  • Существует верхний предел количества предметов, которые могут поместиться в мусорное ведро / рюкзак, независимо от того, какие предметы в нем находятся.

Пример:

Вектор элементов с двумя значениями каждый:

Элементы = [[7,6], [14,2], [27,23], [5,15]]

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

BinOptions = [[64000,1450,350,22000], [8000,450,64,8000]]

Цель состоит в том, чтобы упаковать все предметы наиболее эффективным образом с наименьшими затратами (исходя из стоимости контейнеров / рюкзаков).

Я рассматривал два способа решения проблемы:

  • OR-инструменты с подходом MILP
  • ИЛИ-инструменты с ранцевым решателем

Я не обязательно застрял на OR-Tools, это просто то, с чем я играл, и, судя по отчетам, которые я видел, хорошо работает на разных языках. Было бы неплохо иметь возможность смоделировать это, а потом выбрать язык.

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

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

Ваше здоровье

Лягушка


multidimensional-array knapsack-problem bin-packing or-tools
person The Frog    schedule 17.01.2019    source источник

Ответы (2)


arrow_upward
0
arrow_downward

решатель рюкзака не решит вашу проблему, так как это чистый решатель 1-рюкзака.

Вы можете использовать решатель MILP или CP-SAT.

person Laurent Perron    schedule 17.01.2019
comment
Привет, Лоран, Большое спасибо за ваше руководство. Я очень ценю это. Просто глядя на решатели, может показаться, что CP-SAT - хороший вариант. Я просмотрел несколько примеров, и есть часть, которую я не могу понять. Используя CP-SAT в качестве решателя для MILP в этом контексте, я не уверен, как бы я мог кодировать / выражать корзины / рюкзаки как с несколькими ограничениями, так и с «неограниченным» количеством каждого типа. Есть ли известный вам пример, на который вы можете указать мне? Приветствую и большое спасибо, лягушка - person The Frog; 21.01.2019
comment
Безлимитный может быть действительно большим. Можете ли вы вычислить разумную верхнюю границу? Затем создать одну bool var для каждой пары (элемент, корзина)? - person Laurent Perron; 23.03.2019

arrow_upward
0
arrow_downward

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

 solver = pywraplp.Solver.CreateSolver('SCIP')

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

#> Constraints:
## Each item must be packed once
for i in data['items']:
    solver.Add(sum(x[i, j] for j in data['bins']) == 1)

## The sum of each weight type cannot exceed the capacity for that bin
## You have two weight types, k.
for k in range(2):
    for j in data['bins']:
        solver.Add(
            sum(x[(i, j)] * data['weights'][k][i] for i in data['items']) <= y[j] *
            data['bin_capacity'][k])

## The number of items cannot exceed the numerical capacity of each bin
## Let's assume this capacity is element 2 of data['bin_capacities']
for j in data['bins']:
    solver.Add(
        sum(x[(i, j)] for i in data['items']) <= y[j] * data['bin_capacity'][2])

#> Objective:
## The original objective function used in the example.
solver.Minimize(solver.Sum([y[j] for j in data['bins']]))

## With the addition of a variable cost for a bin, you may need the following.
solver.Minimize(solver.Sum([y[j] * data['bin_cost'] for j in data['bins']]))
person RDavey    schedule 14.12.2020