CODEWITHSUNDEEP
pythonlinear-programmingpulp
kauray
kauray

Reputation: 719

How do I specify the constraints in PuLP Python for multiplying two variables?

I am trying to model the following Integer Programming model using Python PuLP

enter image description here

I have written the following code :

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)

At runtime this provides the error :

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

As far as I can identify, the problem lies in con1 = sum(xs[(i + j*item.bins)]* ys[j] for j in range(item.bins)). How do I specify the constraints?

Upvotes: 3

Views: 7453

Answers (1)

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16724

The message from PuLP is correct. You are trying to pass a non-linear construct (multiplication of two variables) to PuLP while PuLP is designed for linear models only. Fortunately, the simple bin-packing model you want to solve can be formulated as a linear MIP model, see here. Before starting typing some Python code it often helps me to first write down the mathematical model more precise than what you posted (which is too general).

Upvotes: 4

Related Questions