Comment puis-je spécifier les contraintes dans PuLP Python pour multiplier deux variables?

Question

Je suis en train de modéliser le modèle de programmation entier suivant à l'aide Python Pâte à papier

J'ai écrit le code suivant:

from pulp import * 

#knapsack problem 

def knapsolve(item): 

    prob = LpProblem('BinPacking', LpMinimize) 

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

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

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

    print(nbins) 

    #constraints 

    t = nbins >= 1 
    print(t) 
    prob += t 

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

    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 

class Probelm: 
    #bins, binweight, items, weight, itemheight, binheight 

    bins = 5 
    items = 5 

    binweight = [2,3,2,5,3] 
    itemweight = [1,2,2,1,3] 

    itemheight = [2,1,4,5,3] 
    binheight = [4,9,10,8,10] 


item = Problem() 

knapsolve(item) 

Lors de l'exécution de cette offre l'erreur:

y1 + y2 + y3 + y4 + y5 
y1 + y2 + y3 + y4 + y5 >= 1 
Traceback (most recent call last): 
    File "C:\Python34\BinPacking6.py", line 58, in <module> 
    knapsolve(item) 
    File "C:\Python34\BinPacking6.py", line 27, in knapsolve 
    con1 = sum(xs[(i + j*item.bins)]* ys[j] for j in range(item.bins)) 
    File "C:\Python34\BinPacking6.py", line 27, in <genexpr> 
    con1 = sum(xs[(i + j*item.bins)]* ys[j] for j in range(item.bins)) 
    File "C:\Python34\lib\site-packages\pulp-1.6.1-py3.4.egg\pulp\pulp.py", line 209, in __mul__ 
    return LpAffineExpression(self) * other 
    File "C:\Python34\lib\site-packages\pulp-1.6.1-py3.4.egg\pulp\pulp.py", line 786, in __mul__ 
    return self * LpAffineExpression(other) 
    File "C:\Python34\lib\site-packages\pulp-1.6.1-py3.4.egg\pulp\pulp.py", line 774, in __mul__ 
    raise TypeError("Non-constant expressions cannot be multiplied") 
TypeError: Non-constant expressions cannot be multiplied 

Autant que je puisse identifier, le problème réside dans con1 = sum(xs[(i + j*item.bins)]* ys[j] for j in range(item.bins)). Comment puis-je spécifier les contraintes?

Answer 1

Le message de PuLP est correct. Vous essayez de passer une construction non-linéaire (multiplication de deux variables) à PuLP tandis que PuLP est conçu uniquement pour les modèles linéaires. Heureusement, le modèle simple de bin-packing que vous voulez résoudre peut être formulé comme un modèle MIP linéaire, voir here. Avant de commencer à taper du code Python, cela m'aide souvent à écrire d'abord le modèle mathématique plus précis que ce que vous avez posté (ce qui est trop général).