如何在 PuLP Python 中指定约束以将两个变量相乘？

Question

我正在尝试使用 Python PuLP

对以下整数规划模型建模

我写了下面的代码：

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)

在运行时这提供了错误：

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

据我判断，问题出在con1 = sum(xs[(i + j*item.bins)]* ys[j] for j in range(item.bins))。如何指定约束条件？

Answer 1

PuLP 的消息是正确的。您正在尝试将非线性构造（两个变量的乘法）传递给 PuLP，而 PuLP 仅为线性模型设计。幸运的是，您要求解的简单装箱模型可以表示为线性 MIP 模型，请参阅 here。在开始输入一些 Python 代码之前，它通常帮助我首先写下比您发布的更精确的数学模型（这太笼统了）。

如何在 PuLP Python 中指定约束以将两个变量相乘？

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

python

linear-programming

pulp