纸浆 LP 最小化配制“选择一种类型”约束

下面的代码用于运行 LP 最小化问题，其中我们有某些食物、它们的营养价值和成本。该代码当前在所呈现的状态下工作。我正在尝试添加另一种类型的约束。我将所有食物分为不同的类别（早餐、午餐、晚餐、零食）。我想创建一个约束，其中Only 1早餐、午餐和晚餐项目可以选择。 （零食不限）。 “1”和“0”对应于该项目是否是（早餐、午餐、晚餐或小吃），具体取决于它在数组中的位置。

from pulp import *

Food = ["Bacon", "Eggs", "Pancakes", "Waffles", "Yogurt", "Bagels", "Sausage", "Cheerios",
    "Strawberries", "Milk", "OJ", "Oranges", "Apples", "Carrots", "Broccoli","Ham", "Turkey",
    "Steak", "Salmon", "Pasta","Chicken", "Pizza", "Rice", "Salad", "Potatoes"]

nutrition = ["Calories", "Protein", "Sugars", "Cholesterol", "Vitamin_A", "Vitamin_B", "Vitamin_C",
         "Vitamin_K", "Vitamin_E", "Zinc", "Iron", "Fat", "Sodium", "Carbs", "Fiber",
         "Calcium", "Potassium", "Folic_acid", "Thiamin"]

Category = ["Breakfast", "Lunch", "Dinner", "Snack"]

VarCategory = [[1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
               [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0],
               [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1],
               [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
VarCategory = makeDict([Category, Food], VarCategory)


VarNutrition = [[45, 367, 84.3, 212, 250, 72.3, 150, 103, 49, 100, 134, 85.1, 52.8, 5.3, 30.9, 290, 280, 412, 159, 288, 231, 324, 428, 370, 403],
            [3, 24, 2.3, 5.3, 10.7, 2.8, 6, 3.2, 1, 8, 1, 1.3, 0.3, 1.1, 2.6, 18, 18, 21, 24.9, 12, 43.4, 13.9, 19.2, 20, 13.7],
            [0, 4, 0, 5.2, 46.7, 0, 1, 1.1, 7, 13, 23.3, 16.9, 11.1, 0.7, 1.5, 6, 5, 0, 0, 11, 0, 4.1, 13.8, 1, 0],
            [3, 86, 7, 0, 3, 2, 10, 0, 0, 3, 0, 0, 0, 0, 0, 8, 7, 61, 10, 10, 40, 9, 18, 13, 7],
            [0, 23, 2, 20, 2, 1, 4, 16, 0, 10, 2, 8, 1, 41, 11, 6, 6, 0, 2, 10, 1, 6, 41, 10, 34],
            [0, 20, 1, 19, 12, 1, 0, 27, 2, 0, 31, 2.5, 1, 1, 4, 0, 0, 50, 50, 12, 25, 10, 23, 0, 22],
            [0, 1, 1, 2, 3, 0, 0, 11, 149, 0, 62, 139, 7, 1, 135, 35, 35, 0, 0, 10, 0, 0, 17, 30, 81],
            [0, 11, 0,  0,  0,  0,  0,  1,  4,  0,  0,  0,  1,  2,  116, 0, 0,  4,  0,  10, 1,  8,  16, 0,  0],
            [0, 12, 0,  0,  0,  0,  0,  1,  2,  0,  0,  2,  0,  0,  4,  0, 0,   4,  9,  10, 2,  6,  4,  0,  0],
            [0, 15, 1,  3,  12, 1,  0,  30, 1,  0,  0,  1,  0,  0,  2,  0,  0, 69,  3,  10, 9,  10, 9,  0,  14],
            [0, 15, 4,  20, 1,  6,  4,  49, 3,  0,  2,  1,  0,  1,  4,  20, 20, 28, 6,  10, 8,  16, 7,  8,  18],
            [6, 41, 5,  11, 4,  1,  22, 3,  1,  4,  0,  1,  0,  0,  1,  8,  7, 25,  9,  20, 8,  19, 8,  29, 33],
            [6, 26, 7,  12, 6,  5,  15, 8,  0,  5,  0,  0,  0,  0,  1,  53, 42, 3,  44, 50, 4,  25, 47, 59, 20],
            [0, 2,  4,  11, 16, 5,  0,  7,  4,  4,  11, 7,  5,  0,  2,  15, 15, 0,  0,  10, 0,  13, 25, 10, 16],
            [0, 0,  0,  8,  0,  2,  0,  11, 12, 0,  2,  18, 6,  2,  9,  16, 16, 0,  0,  30, 0,  7,  10, 0,  0],
            [0, 16, 8,  4,  37, 0,  2,  11, 2,  30, 0,  8,  1,  0,  4,  6,  6, 1,   1,  0,  2,  15, 4,  4,  34],
            [0, 9,  1,  4,  14, 1,  0,  5,  7,  0,  3,  9,  3,  1,  8,  0,  0, 14,  7,  10, 10, 6,  12, 0,  41],
            [0, 17, 3,  10, 6,  6,  0,  68, 9,  0,  2,  8,  0,  1,  14, 0,  0, 5, 1,    20, 1,  0,  15, 0,  15],
            [0, 8,  5,  21, 6,  9,  0,  36, 2,  0,  63, 12, 1, 0,   4,  0,  0, 9,   2,  10, 7,  14, 17, 0,  18]]
VarNutrition = makeDict([nutrition, Food], VarNutrition)

ConstraintsLow = [2000, 72, 0, 85, 100, 100, 100, 100, 100, 0, 0, 0, 0, 90, 100, 100, 100, 100, 100]
ConstraintsLow = makeDict([nutrition],ConstraintsLow)



Cost = [1.22,   1.56,   6.79,   6.79,   1.00,   2.50,   2.00,   0.14,   1.37,   1.69, 1.99, 0.50,   0.50,   0.50,   0.50,   4.25,   4.25,   4.00,   5.00,   7.00, 3.18, 1.25,   5.00,   6.00,   3.00]
Cost = makeDict([Food], Cost)

prob = LpProblem("Nutrition Calculator", LpMinimize)

vars = LpVariable.dicts("Servings of", (Food), 0, None, LpContinuous)
Svars = LpVariable.dicts("Food Chosen", (Category, Food), 0, None, LpBinary)

prob += lpSum(vars[i]*Cost[i] for i in Food )

for j in nutrition:
    prob += lpSum([vars[i]*VarNutrition[j][i] for i in Food]) >= ConstraintsLow[j]


for i in Food:
    prob += vars[i] >= 0
    prob += vars[i] <= 2




print (prob)
prob.writeLP("Nutrition.lp")
prob.solve()
print ("Status:", LpStatus[prob.status])
for v in prob.variables():
    print (v.name, "=", v.varValue)
print ("Total Cost = ", value(prob.objective))

我遇到的问题是创建这样的约束。我想使用二进制变量，但我不知道如何实现。任何帮助，将不胜感激

您应该做的是为所选的每种食物设置二元变量，然后约束它们的总和为 1——这意味着其中一个二元变量为 1，其他为 0。

问题在于，例如，打开早餐二进制变量意味着线性程序中存在 if-then 条件。如果至少选择了一项早餐，则早餐为 1，否则为 0。if-then 语句不是线性的，因此我们需要一种巧妙的方法来使其呈线性。我们可以通过“大 M 约束”来做到这一点。

让Python变量代表每种食物的决策总和，例如breakfast_sum, lunch_sum etc.

然后制作 PuLP 二进制变量breakfast_binary, lunch_binary etc.

我们将使用一个大的 M 约束来获得breakfast_binary“翻转”时breakfast_sum大于 0。然后我们将使用另一个约束来确保二元变量的总和

M基本上是一个大数。它需要有多大？请注意，您永远不会为每种早餐分配超过 2 份，因此请尝试使 M = 2 * {早餐项目数量}。现在看看这个约束：

M * breakfast_binary >= breakfast_sum.

If breakfast_sum是 0，那么breakfast_binary is allowed为 0。一旦您分配一份早餐食品，breakfast_binary被迫翻转到1。

在午餐、晚餐等时执行此操作，然后有一个额外的约束，即二元变量的总和

这个答案自由地解释了第 4 章“优化建模”数据智能作者：约翰·福尔曼。我强烈推荐它。