时间戳

首页 > 解决方案 > 具有非线性约束的优化问题

python - 具有非线性约束的优化问题

问题描述

我是优化问题的新手，正在研究一个简单的最大化问题，我可以在 Excel 中非常简单地解决这个问题。但是，我需要在 Python 中对其进行扩展并需要一些帮助。

我有一份包含不同食物的菜单，我需要最大限度地提高能量输出。例子：

宏 食物 卡路里 活力
蛋白质 鱼 100 60
蛋白质 羊肉 200 40
蛋白质 蛋 200 38
碳水化合物 香蕉 200 25
碳水化合物 土豆 200 30
碳水化合物 米 200 40
胖的 牛油果 450 50
胖的 奶酪 400 60
胖的 奶油 500 55

鉴于以下约束，我需要最大化能量（e）：

  1. 每个宏 (m) 只能消耗 1 个食物项目 (i)。所以我需要一个指示变量 (0/1) 来从 m - 蛋白质、脂肪和碳水化合物中的每一个中选择一个。
  2. 卡路里总数 (c) 不应超过一个常数值 假设每个项目 1 份（对此不需要限制）

问题表述：

变量： X (m,i) → 二进制变量 = {1，如果宏 m 和项目 i 被选择，0 否则}

最大化 e(m,i) * X(m,i)

参数：卡路里 (C) -> 每个卡路里 (Macro, fooditem)

受约束：对于每个 m，Σ X (m,i) <= 1（每个宏只能选择 1 个项目）Σ c(m,i) * X(m,i)/ X(i) <= N（卡路里消耗限于常数 N）

到目前为止，我认为这是一个具有非线性约束的混合整数问题。

  1. 我曾尝试使用 Pulp，但由于非线性约束而失败。如果我删除非线性，它可以正常工作。
  2. 我尝试使用 Scipy Optimize，但 Scipy 不允许创建整数变量。

如何使用 Python 解决这个问题？我在这里误解了问题吗？

更新： 上面缺少由于mean. 我将问题从对 的约束更新为对total的约束mean。在非数学术语中，我取所有宏相乘后得到的数字的平均值，因为我希望我的平均卡路里小于常数 N。

所以在数学上，Σ c(m,i) * X(m,i)/ X(i) <= N（平均卡路里消耗限制在常数 N）

标签： pythonlinear-programmingpulpscipy-optimizemixed-integer-programming

解决方案

正如您已经提到的，scipy.optimize.minimize无法处理混合整数问题 (MIP)。最多可以做的是尝试通过一种惩罚方法来解决 MIP，即在目标上添加一个惩罚函数，例如1.0/eps * np.sum(x*(1 - x))，其中eps > 0是给定的惩罚参数和xa np.ndarray。

但是，使用 MIP 求解器解决问题要方便得多。由于您的问题具有众所周知的类似背包的结构，因此即使是非商业 MIP 求解器（PuLp 默认使用 CBC）也可以利用问题的底层结构。在这里，我推荐以下公式：

Binary variables:
x[i] = 1 if fooditem i is chosen, 0 otherwise

Parameters:
a[i][m] = 1 if fooditem i covers macro m, 0 otherwise
c[i]        calories for fooditem i
e[i]        energy for fooditem i
N           total calories limit

Model:

max Σ (e[i] * a[i][m] * x[i],  ∀ i ∈ Fooditems, m ∈ Macros)

s.t. Σ (a[i][m] * x[i], ∀ i ∈ Fooditems) <= 1  ∀ m ∈ Macros. (1)
     Σ (c[i] * x[i], ∀ i ∈ Fooditems)    <= N                (2)

可以像这样建模和解决：

import pulp

fooditems = {
    'Fish':    {'macro': 'Protein', 'calorie': 100, 'energy': 60},
    'Lamb':    {'macro': 'Protein', 'calorie': 200, 'energy': 40},
    'Egg':     {'macro': 'Protein', 'calorie': 200, 'energy': 38},
    'Banana':  {'macro': 'Carbs',   'calorie': 200, 'energy': 25},
    'Potato':  {'macro': 'Carbs',   'calorie': 200, 'energy': 30},
    'Rice':    {'macro': 'Carbs',   'calorie': 200, 'energy': 40},
    'Avocado': {'macro': 'Fat',     'calorie': 450, 'energy': 50},
    'Cheese':  {'macro': 'Fat',     'calorie': 400, 'energy': 60},
    'Cream':   {'macro': 'Fat',     'calorie': 500, 'energy': 55},
}

# parameters
macros = list({fooditems[i]['macro'] for i in fooditems})
a = {item: {m: 1 if m == fooditems[item]['macro']
            else 0 for m in macros} for item in fooditems}
c = {item: fooditems[item]['calorie'] for item in fooditems}
e = {item: fooditems[item]['energy'] for item in fooditems}
N = 1000

# pulp model
mdl = pulp.LpProblem("bla", pulp.LpMaximize)

# binary variables
x = pulp.LpVariable.dicts("x", fooditems, cat="Binary")

# objective
mdl.setObjective(sum(e[i] * a[i][m] * x[i] for m in macros for i in fooditems))

# constraints (1)
for m in macros:
    mdl.addConstraint(sum(a[i][m]*x[i] for i in fooditems) <= 1)

# constraints (2)
mdl.addConstraint(sum(x[i]*c[i] for i in fooditems) <= N)

# solve the problem
mdl.solve()

print(f"Status: {pulp.LpStatus[mdl.status]}")
for var in mdl.variables():
    print(f"{var.name} = {var.varValue:.0f}")
print(f"energy: {mdl.objective.value()}")

这产生

Status: Optimal
x_Avocado = 0.0
x_Banana = 0.0
x_Cheese = 1.0
x_Cream = 0.0
x_Egg = 0.0
x_Fish = 1.0
x_Lamb = 0.0
x_Potato = 0.0
x_Rice = 1.0
Energy: 160.0

推荐阅读