Requête Python pour l'empaquetage avec le coût et les tailles des bacs variables

Question

Je travaille actuellement sur un problème qui nécessite une variation du problème d'emballage des bacs. Mon problème est différent en ce que le nombre de bacs est fini. J'ai trois bacs, le plus petit coûte le moins cher de mettre un objet, le bac moyen est un peu plus cher que la petite boîte, et la troisième boîte a théoriquement une capacité illimitée, mais il est prohibitivement plus cher de placer un objet.

J'ai été en mesure de trouver un script Python en ligne qui résout le problème bin de la même manière. Ma question est comment puis-je réécrire le script pour se rapprocher de mon problème d'origine? Le script en question utilise des bacs identiques.

J'ai inclus quelques lignes tout en bas pour discuter de la façon dont je préférerais que la poubelle soit regardée. De plus, existe-t-il un moyen de définir des contraintes distinctes pour chaque bac? Merci pour votre aide!

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

La variante du problème d'empaquetage des bacs avec les tailles de bacs variables que vous décrivez est au moins np-hard.

Je ne connais pas le paquet openopt, le site du projet semble être en panne. Openopt semble utiliser GLPK pour résoudre le problème en tant que programme mixte. Vous n'avez pas d'accès direct à la formulation du modèle, puisque BPP() est une abstraction. Vous devrez peut-être modifier le paquet openopt pour ajouter des contraintes pour les différents bacs.

Il est généralement facile d'ajouter les tailles de casiers variables comme une contrainte, en étendant this formulation vous auriez besoin d'ajouter l'indice i à la capacité V, de sorte que chaque casier ait une capacité différente.

Je recommanderais d'examiner quelques bibliothèques maintenues pour modéliser et résoudre ce problème: Il y a la bibliothèque PuLP, CyLP et SCIP. Ce dernier n'est pas gratuit pour un usage commercial, je pense cependant.

Depuis l'emballage de la corbeille est un problème très commun, j'ai trouvé un exemple pour la bibliothèque PuLP. Il utilise le solveur de CoinOR par défaut je pense, vous pouvez également utiliser différents commerciaux.

easy_install pulp 

Après l'installation de pâtes et papiers, qui devrait être possible avec easy_install vous pouvez étendre sur this example. J'ai modifié l'exemple en fonction de votre problème:

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)) 

Cette mise en œuvre a l'avantage fort que vous avez un contrôle total sur la formulation de votre modèle et vous n'êtes pas limité par une couche d'abstraction comme BPP() dans le cas de openopt.