Bin packen Python-Abfrage mit variablen Lagerplatzkosten und Größen

Question

Ich arbeite derzeit an einem Problem, das eine Variation des Fach Verpackung Problem erfordert. Mein Problem ist, dass die Anzahl der Bins endlich ist. Ich habe drei Behälter, der kleinste kostet am wenigsten, einen Gegenstand hineinzulegen, der mittlere Behälter ist etwas teurer als der kleine Behälter, und der dritte Behälter hat theoretisch unbegrenzte Kapazität, ist aber unerschwinglich teurer, um einen Gegenstand hineinzustellen.

Ich konnte ein Python-Skript online finden, das das Bin-Problem in ähnlicher Weise löst. Meine Frage ist, wie kann ich das Skript umschreiben, um meinem ursprünglichen Problem näher zu kommen? Das fragliche Skript verwendet identische Bins.

Ich habe ein paar Zeilen ganz unten eingefügt, um zu besprechen, wie ich das Fach aussehen würde. Gibt es außerdem eine Möglichkeit, separate Einschränkungen für jeden Bereich einzurichten? Danke für die Hilfe!

from openopt import * 

N = 30 #Length of loan dataset 

items = [] 
for i in range(N): 
    small_vm = { 
     'name': 'small%d' % i, 
     'cpu': 2, 
     'mem': 2048, 
     'disk': 20, 
     'n': 1 
     } 
    med_vm = { 
     'name': 'medium%d' % i, 
     'cpu': 4, 
     'mem': 4096, 
     'disk': 40, 
     'n': 1 
     } 
    large_vm = { 
     'name': 'large%d' % i, 
     'cpu': 8, 
     'mem': 8192, 
     'disk': 80, 
     'n': 1 
     } 
    items.append(small_vm) 
    items.append(med_vm) 
    items.append(large_vm) 



bins = { 
'cpu': 48*4, # 4.0 overcommit with cpu 
'mem': 240000, 
'disk': 2000, 
} 

p = BPP(items, bins, goal = 'min') 

r = p.solve('glpk', iprint = 0) 
print(r.xf) 
print(r.values) # per each bin 
print "total vms is " + str(len(items)) 
print "servers used is " + str(len(r.xf)) 

for i,s in enumerate(r.xf): 
    print "server " + str(i) + " has " + str(len(s)) + " vms" 




##OP Interjection: Ideally my bins would look something like: 
bin1 = { 
    'size': 10000, 
    'cost': 0.01*item_weight, 
    } 

bin2 = { 
    'size': 20000, 
    'cost': 0.02*item_weight, 
    } 

bin3 = { 
    'size': 100000, 
    'cost': 0.3*item_weight, 
    } 

Answer 1

Die Variante des Fachpackungsproblems mit variablen Fachgrößen, die Sie beschreiben, ist mindestens np-schwer.

Ich weiß nicht, das Paket openopt, scheint die Projektwebsite zu sein. Openopt scheint GLPK zu verwenden, um das Problem als ein gemischt-ganzzahliges Programm zu lösen. Sie haben keinen direkten Zugriff auf die Modellformulierung, da BPP() eine Abstraktion ist. Möglicherweise müssen Sie das openopt-Paket ändern, um Einschränkungen für die einzelnen Klassen hinzuzufügen.

Es ist im Allgemeinen einfach, die variablen Behältergrößen als Einschränkung hinzuzufügen, wobei this formulation erweitert wird. Sie müssten den Index i zur Kapazität V hinzufügen, so dass jeder Behälter eine andere Kapazität hat.

Ich würde empfehlen, einige gepflegte Bibliotheken zu modellieren und dieses Problem zu lösen: Es gibt die Bibliothek PuLP, CyLP und SCIP. Letzteres ist nicht frei für kommerzielle Nutzung, denke ich aber.

Da bin Packing ein sehr häufiges Problem ist, fand ich ein Beispiel für die PuLP-Bibliothek. Es verwendet standardmäßig den CoinOR Solver. Ich denke, Sie können auch verschiedene kommerzielle verwenden.

easy_install pulp 

Nach PULP Installation, die mit möglich sein sollte easy_install Sie auf this example erweitern können. I modifiziert, um das Beispiel nach Ihrem Problem:

from pulp import * 

items = [("a", 5), ("b", 6), ("c", 7)] 

itemCount = len(items) 
maxBins = 3 
binCapacity = [11, 15, 10] 
binCost = [10, 30, 20] 

y = pulp.LpVariable.dicts('BinUsed', range(maxBins), lowBound = 0, upBound = 1, cat = pulp.LpInteger) 
possible_ItemInBin = [(itemTuple[0], binNum) for itemTuple in items for binNum in range(maxBins)] 
x = pulp.LpVariable.dicts('itemInBin', possible_ItemInBin, lowBound = 0, upBound = 1, cat = pulp.LpInteger) 

# Model formulation 
prob = LpProblem("Bin Packing Problem", LpMinimize) 

# Objective 
prob += lpSum([binCost[i] * y[i] for i in range(maxBins)]) 

# Constraints 
for j in items: 
    prob += lpSum([x[(j[0], i)] for i in range(maxBins)]) == 1 
for i in range(maxBins): 
    prob += lpSum([items[j][1] * x[(items[j][0], i)] for j in range(itemCount)]) <= binCapacity[i]*y[i] 
prob.solve() 

print("Bins used: " + str(sum(([y[i].value() for i in range(maxBins)])))) 
for i in x.keys(): 
    if x[i].value() == 1: 
     print("Item {} is packed in bin {}.".format(*i)) 

Diese Implementierung hat den großen Vorteil, dass Sie die vollständige Kontrolle über Ihre Modellformulierung haben, und Sie werden durch eine Abstraktionsschicht wie BPP() im Fall nicht eingeschränkt von openopt.