PuLP'de Tamsayı Programlamayı kullanarak çoklu değişken kısıtlamaları nasıl belirleyebilirim?

Question

Python PuLP'de Tamsayılı Programlama Formülasyonunu kullanarak Bin Paketleme Problemini çözmeye çalışıyorum. bir kod örneğini çalıştırmak ben hamuru kütüphanesi İşte

from pulp import * 

#knapsack problem 

def knapsolve(bins, binweight, items, weight): 

    prob = LpProblem('BinPacking', LpMinimize) 

    y = [LpVariable("y{0}".format(i+1), cat="Binary") for i in range(bins)] 

    xs = [LpVariable("x{0}{1}".format(i+1, j+1), cat="Binary") 
      for i in range(items) for j in range(bins)] 

    #minimize objective 
    nbins = sum(y) 
    prob += nbins 

    print(nbins) 

    #constraints 

    prob += nbins >= 1 

    for i in range(items): 
     con1 = sum(xs[(i * bins) + j] for j in range(bins)) 
     prob += con1 == 1 
     print(con1) 

    for k in range(bins): 
     x = xs[k*bins : (k+1)*bins] 
     con1 = sum([x1*y for x1, y in zip(x, weight)]) 
     prob += con1 <= binweight[k] 
     print(con1) 

    exec('prob') 

    status = prob.solve() 

    print(LpStatus[status]) 
    print("Objective value:", value(prob.objective)) 
    print ('\nThe values of the variables : \n') 

    for v in prob.variables(): 
     print(v.name, "=", v.varValue) 

    return 

def knapsack(): 

    #bins 

    bins = int(input ('Enter the upper bound on the number of bins:')) 

    print ('\nEnter {0} bins\' capacities one by one'.format(bins)) 

    binweight = [] 

    for i in range(0, bins): 
     print('Enter {0} bin capacity'.format(i+1)) 
     binweight.append(int(input())) 

    for i in range(0, bins): 
     print('The capacity at {0} is {1}'.format(i, binweight[i])) 

    #items 

    items = int(input('Enter the number of items:')) 

    weight = [] 

    print ('\nEnter {0} items weights one by one'.format(items)) 

    for i in range(0, items): 
     print('Enter {0} item weight'.format(i+1)) 
     weight.append(int(input())) 

    for i in range(0, items): 
     print('The weight at {0} is {1}'.format(i, weight[i])) 

    knapsolve(bins, binweight, items, weight) 

    return 

knapsack() 

kullanarak aşağıdaki Python kodu yazdım

geçerli::

Enter the upper bound on the number of bins:3 

Enter 3 bins' capacities one by one 
Enter 1 bin capacity 
6 
Enter 2 bin capacity 
4 
Enter 3 bin capacity 
5 
The capacity at 0 is 6 
The capacity at 1 is 4 
The capacity at 2 is 5 
Enter the number of items:3 

Enter 3 items weights one by one 
Enter 1 item weight 
5 
Enter 2 item weight 
1 
Enter 3 item weight 
2 
The weight at 0 is 5 
The weight at 1 is 1 
The weight at 2 is 2 
y1 + y2 + y3 
x11 + x12 + x13 
x21 + x22 + x23 
x31 + x32 + x33 
5*x11 + x12 + 2*x13 
5*x21 + x22 + 2*x23 
5*x31 + x32 + 2*x33 
Optimal 
Objective value: 1.0 

The values of the variables : 

x11 = 0.0 
x12 = 1.0 
x13 = 0.0 
x21 = 0.0 
x22 = 0.0 
x23 = 1.0 
x31 = 0.0 
x32 = 1.0 
x33 = 0.0 
y1 = 0.0 
y2 = 0.0 
y3 = 1.0 

aşağıdaki gibi sorunu için bir modeldir

Çıktı beklendiği gibi değil. Doğru çıktıyı elde etmek için yukarıdaki kısıtlamaları doğru şekilde nasıl belirleyebilirim?

Answer 1

Sorunu inşa sonra bir dosyaya yazarak çıkan LP/MIP modelini kontrol edebilirsiniz:

\* BinPacking *\ 
Minimize 
OBJ: y1 + y2 + y3 
Subject To 
_C1: y1 + y2 + y3 >= 1 
_C2: x11 + x12 + x13 = 1 
_C3: x21 + x22 + x23 = 1 
_C4: x31 + x32 + x33 = 1 
_C5: 5 x11 + x12 + 2 x13 <= 6 
_C6: 5 x21 + x22 + 2 x23 <= 4 
_C7: 5 x31 + x32 + 2 x33 <= 5 
Binaries 
x11 
x12 
x13 
x21 
x22 
x23 
x31 
x32 
x33 
y1 
y2 
y3 
End 

: Eğer binpacking dosyası bakmak Şimdi eğer

... 
prob.writeLP("binpacking") 
status = prob.solve() 
... 

Depo kapasitesi kısıtlamaları doğru değildir. Tüm kutular değişkenlere 1 atanmadan kullanılır. Bunun nedeni, öğe ağırlıklarını kullanırken y değerinin üzerine yazmanızdır.

Böyle olanlar kısıtlamaları değiştirmek gerekir: şöyle

for k in range(bins): 
    x = xs[k*bins : (k+1)*bins] 
    con1 = sum([x1*w for x1, w in zip(x, weight)]) 
    prob += con1 <= binweight[k] * y[k] 
    print(con1) 

Şimdi modellenmiş olacak:

_C5: 5 x11 + x12 + 2 x13 - 6 y1 <= 0 
_C6: 5 x21 + x22 + 2 x23 - 4 y2 <= 0 
_C7: 5 x31 + x32 + 2 x33 - 5 y3 <= 0 

Ayrıca ürün kısıtlamaları nedeniyle endeksleri doğru değil. Bunun yerine x11 + x12 + x13 = 1 arasında o x11 + x21 + x31 = 1

Böyle düzeltebilirsiniz olmalıdır:

for i in range(items): 
    con1 = sum(xs[(i + j*bins)] for j in range(bins)) 
    prob += con1 == 1 
    print(con1) 

kısıtlamalar olacaktır:

_C2: x11 + x21 + x31 = 1 
_C3: x12 + x22 + x32 = 1 
_C4: x13 + x23 + x33 = 1