Упаковка небольшого количества пакетов в фиксированное количество ящиков

У меня есть список размеров упаковки. Будет максимум около 5 различных размеров, и они могут встречаться несколько раз (<50).

packages = [5,5,5,5,5,5,10,11]

Мне нужно упаковать их в фиксированное количество ящиков, например 3.

number_of_bins = 3

Ячейки могут различаться по размеру (сумме размеров упакованных упаковок) от 0 до, скажем, 2 (то есть разница суммы размеров упаковок в ящиках должна быть равной или почти равной). Таким образом, наличие бункеров с [1,2] (= 3) и [2] (= 2) (разница 1) - это нормально, а с [10] (= 10) и [5] (= 5) (разница 5) - нет.

Можно не сортировать все пакеты по ячейкам, но мне нужно решение, при котором минимальное количество пакетов остается распакованным.

Так что лучшим решением в этом случае (я думаю) было бы

bins = [11,5],[10,5],[5,5,5]
remaining = [5]

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

Есть ли какой-нибудь эффективный способ легко это сделать? Я просто пропустил соответствующий поисковый запрос, чтобы найти его?


Другой пример:

packages = [5,10,12]
number_of_bins = 2

приводит к

bins = [12],[10]
remaining = [5]

потому что

bins = [12],[10,5]

имеет размер корзины 12 и 15, которые различаются более чем на 2.

Аналог:

packages = [2,10,12]
number_of_bins = 3

приводит к

bins = [2],[],[]
remaining = [12,10]

Не уверен, что понимаю. Почему [11,5],[10,5,5],[5,5,5] не может быть более оптимальным решением?

Roelant 31.10.2018 14:21

В вашем описании предполагается, что размер пакета игнорируется. Вы хотели написать, что размер бункера варьируется от 0 до 20?

alexis 31.10.2018 14:22

@Roelant Я имел в виду, что размер того, что находится в корзинах, не должен отличаться более чем на 2. Так что мой пример имеет размеры 16,15,15, у вас 16,20,15 и 20-15 больше 2.

DonQuiKong 31.10.2018 14:24

@alexis Я попытался уточнить, размер корзины не имеет значения, только сумма размеров пакетов в корзине.

DonQuiKong 31.10.2018 14:24

Подождите, вы пытаетесь сказать, что разница в общем размере каждой корзины до следующей следует ограничить? Таким образом, каждая ячейка может стать сколь угодно большой, если разница между ними невелика. Это было совсем не ясно (правда, до сих пор). Обычно предполагается, что ограничением является максимальная вместимость каждого бункера.

alexis 31.10.2018 18:58

@alexis да, именно так. Я не знаю, как это выразить яснее. Есть предел для бункеров, но в этой части он недостижим. Я добавляю больше вещей позже (в том числе и в других измерениях), и тогда я достигаю предела, так что я могу полностью игнорировать это здесь.

DonQuiKong 31.10.2018 19:15
0
6
531
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

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

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

import numpy as np

def int_to_base_list(x, base, length):
    """ create a list of length length that expresses a base-10 integer
        e.g. binary: int2list(101, 2, 10) returns array([0, 0, 0, 1, 1, 0, 0, 1, 0, 1])
    """
    placeholder = np.array([0] * length)  # will contain the actual answer
    for i in reversed(range(length)):
        # standard base mathematics, see http://www.oxfordmathcenter.com/drupal7/node/18
        placeholder[i] = x % base  
        x //= base
    return placeholder

def get_groups(packages, max_diff_sum, number_of_bins):
    """ Get number_of_bins packaging groups that differ no more than max_diff_sum
        e.g. 
        [5, 5, 5, 5, 5, 5, 10, 11] with 2, 3 gives [5,5,5], [10,5], [11,5]
        [5, 10, 12] with 2, 2 gives [10], [12]
        [2, 6, 12] with 2, 3 gives [2], [], []

        We approach the problem by iterating over group indices, so the first
        example above has solution [0 0 0 1 2 3 1 2] with the highest number being
        the 'remainder' group. 
    """
    length = len(packages)
    for i in range((number_of_bins + 1)**length - 1):  # All possible arrangements in groups 
        index = int_to_base_list(i, number_of_bins + 1, length)  # Get the corresponding indices
        sums_of_bins = [np.sum(packages[index==ii]) for ii in range(number_of_bins)]
        if max(sums_of_bins) - min(sums_of_bins) <= max_diff_sum:  # the actual requirement 
            # print(index)
            break
    groups = [packages[index==ii] for ii in range(number_of_bins)] 
    # remainder = packages[index==number_of_bins+1]
    return groups

На ваших примерах:

packages = np.array([5, 5, 5, 5, 5, 5, 10, 11])
max_diff_sum = 2
number_of_bins = 3
get_groups(packages, max_diff_sum, number_of_bins)

>> [array([5, 5, 5]), array([ 5, 10]), array([ 5, 11])]

А также

packages = np.array([5,10,12])
max_diff_sum = 2
number_of_bins = 2
get_groups(packages, max_diff_sum, number_of_bins)

>> [array([10]), array([12])]

Я попробую это сделать, вероятно, не раньше пятницы (пора идти), и доложу. Достаточно ли быстро, чтобы пройти до 50 (а возможно, и меньше) пакетов в 6 ящиках?

DonQuiKong 31.10.2018 16:33

@DonQuiKong это означало бы 6 ** 50, так что нет

juvian 31.10.2018 16:47

Я попробовал раствор для целлюлозы, а этот с 40 пакетами и 6 корзинами, версия для целлюлозы работала менее 2 секунд, затем я пошел выпить кофе и немного поболтать, а этот еще не закончился, когда я вернулся. В любом случае спасибо, но похоже, что это сработает только в том случае, если кто-то каким-то образом использует тот факт, что большинство пакетов будут иметь размер, выбираемый, может быть, из 3 или 4 разных размеров. Но мне нравится перебирать список ящиков для каждого пакета, это хороший трюк. Просто мозговой штурм: можно было бы векторизовать цикл for, чтобы значительно повысить производительность.

DonQuiKong 02.11.2018 09:26
Ответ принят как подходящий

Вот решение с использованием мякоть:

from pulp import *

packages = [18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 65, 65, 65]
number_of_bins = 3
bins = range(1, number_of_bins + 1)
items = range(0, len(packages))

x = LpVariable.dicts('x',[(i,b) for i in items for b in bins],0,1,LpBinary)
y = LpVariable('y', 0, 2, LpInteger)
prob=LpProblem("bin_packing",LpMinimize)

#maximize items placed in bins
prob.setObjective(LpAffineExpression([(x[i,b], -3) for i in items for b in bins] + [(y, 1)]))

#every item is placed in at most 1 bin
for i in items:
    prob+= lpSum([x[i,b] for b in bins]) <= 1

for b in bins:
    if b != 1: # bin 1 is the one with lowest sum
        prob+= LpAffineExpression([(x[i,b], packages[i]) for i in items]  + [(x[i,1], -packages[i]) for i in items])  >= 0
    if b != number_of_bins: # last bin is the one with highest
        prob+= LpAffineExpression([(x[i,number_of_bins], packages[i]) for i in items]  + [(x[i,b], -packages[i]) for i in items])  >= 0

#highest sum - lowest sum <= 2 so every difference of bin sums must be under 2
prob += LpAffineExpression([(x[i,number_of_bins], packages[i]) for i in items]  + [(x[i,1], -packages[i]) for i in items]) <= 2  
prob += LpAffineExpression([(x[i,number_of_bins], packages[i]) for i in items]  + [(x[i,1], -packages[i]) for i in items]) == y

prob.solve()
print(LpStatus[prob.status])

for b in bins:
    print(b,':',', '.join([str(packages[i]) for i in items if value(x[i,b]) !=0 ]))
print('left out: ', ', '.join([str(packages[i]) for i in items if sum(value(x[i,b]) for b in bins) ==0 ]))

Это просто здорово! Большое спасибо! Можно ли легко минимизировать значение (размер) остатка и, возможно, даже разницу между ячейками без потери производительности? Это была бы особенность приятно иметь ;-)

DonQuiKong 02.11.2018 09:22

@DonQuiKong на данный момент скрипт минимизирует количество элементов, оставленных вне ящиков, вместо этого вы хотели бы минимизировать сумму размеров оставленных элементов? Сведение к минимуму различий между ячейками невозможно с этой моделью, потому что мы можем минимизировать только одну функцию, а остальные являются ограничениями. Однако вы можете легко выполнить цикл от 0 до 2 и запустить код с ограничением разницы между значениями ячеек и решить каждую из этих трех проблем, а затем сравнить результаты в соответствии с вашими потребностями.

juvian 02.11.2018 15:16

Не вместо этого, а дополнительно. Но я только что обнаружил, что ввод списка с обратной сортировкой поможет. (Пример: ´ [18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 65, 65, 65] ´ возвращает ´bins [[65 , 18, 18, 18, 18, 18, 18, 18, 18], [18, 18, 65, 18, 18, 18, 18, 18, 18]] и остаток [65] ´, однако если вход отсортировано, чтобы начать с 65, остаток будет [18] (а ячейки разные).

DonQuiKong 02.11.2018 15:43

Блин, как ты код в комментариях делаешь? Просто нечитабельно, извините, пробовал. В любом случае, я также думал об изменении "prob.setObjective (lpSum ([x [i, b] for i in items for b in bins])" на что-то вроде prob.setObjective (100000000 * lpSum ([x [i, b] для i в элементах для b в ячейках] + lpSum ([i для i в элементах для b в ячейках])), который также должен помочь? Но я не знаю, как это работает, и сортировка кажется прекрасной.

DonQuiKong 02.11.2018 15:46

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

juvian 02.11.2018 15:55

Я не очень склонен запускать его в другой раз, потому что мне нужно, чтобы программа завершилась за разумный промежуток времени, и у меня уже есть проблемы с этим (он идет вверх и вниз). Но спасибо за помощь, я поиграю с этим еще, это именно то, что мне нужно, чтобы все заработало.

DonQuiKong 02.11.2018 16:05

@DonQuiKong, разве это не заняло 2 секунды? Насколько быстро вам это нужно: o

juvian 02.11.2018 16:15

Кажется, это немного отличается в зависимости от ввода. Но даже 2 секунды - это много, если вы запустите его 200 раз;) Я начал группировать пакеты в более крупные пакеты, что значительно ускоряет его. Например. если number_of_bins равно 3, то никогда не должно быть более 5 экземпляров пакета ([1,1,1,1,1]), потому что если будет 6 раз больше 1, то [2,1,1,1,1] будет идентичный. делает это намного быстрее, если существует 15 или около того экземпляров 1 пакета для 2 или 3 ящиков.

DonQuiKong 02.11.2018 16:20

@DonQuiKong дайте мне пример, который требует "много", и я могу попробовать несколько вещей

juvian 02.11.2018 16:34

[18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 65, 65, 65], распределенная по 3 корзинам, занимает немного больше минуты (в режим отладки). Но все в порядке, я меняю ввод на [72, 65, 65, 65, 36, 36, 36, 36, 18, 18, 18, 18], что снижает его до 0,7 секунды в режиме отладки и имеет те же решения.

DonQuiKong 02.11.2018 16:46

@DonQuiKong занимает 14 секунд без режима отладки на моем компьютере. Модифицированный код, позволяющий ограничить разницу меньшими ограничениями (n вместо n ^ 2). Сейчас работает за 4,3 с. Вы также можете попробовать изменить решатель

juvian 02.11.2018 17:20

@DonQuiKong 0.4s теперь, а также оптимизирует разницу между ячейками, если есть связь по оставленным элементам ^^

juvian 02.11.2018 18:27

приятно :) попробую в понедельник

DonQuiKong 02.11.2018 18:30

Я адаптировал его, чтобы минимизировать сумму оставленных пакетов с y = pulp.LpVariable('y', 0, max(packages), pulp.LpInteger) и prob += pulp.LpAffineExpression([(x[i,b], packages[i]) for i in items for b in bins]) == sum(packages) - y, но как вы думаете, есть ли способ заставить его предоставить мне все решения с тем же количеством оставшихся пакетов? (Спасибо еще раз за помощь)

DonQuiKong 05.11.2018 15:10

@DonQuiKong в одну сторону - используя SCIP

juvian 05.11.2018 15:26

Другие вопросы по теме