非线性约束优化问题

Question

我对优化问题不熟悉，并且正在研究一个简单的最大化问题，我可以用Excel非常简单地解决这个问题。但是，我需要用Python扩展它，并且需要一些帮助

我有一份不同食物的菜单，我需要最大化我的能量输出。例如：

^{tb1}$

考虑到以下约束条件，我需要最大化能量（e）：

1. 每个宏（m）只能消费1种食物（i）。所以我需要一个指标变量（0/1）来从每种m-蛋白质、脂肪和碳水化合物中只选择1
2. 卡路里总数（c）不应超过一个恒定值 假设每个项目有一部分（无需约束）

问题表述：

变量： X（m，i）→ 二进制变量 ={1，如果选择了宏m和项目i，则为0，否则为}

最大化e（m，i）*X（m，i）

参数： 卡路里（C）——>；每种食物的卡路里（宏量、食物量）

受限制： 对于每m，∑X（m，i）<；=1（每个宏只能选择1项） ∑c（m，i）*X（m，i）/X（i）<；=N（热量消耗限制为常数N）

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

1. 我曾尝试使用纸浆，但由于非线性约束，它失败了。如果我去掉非线性，它工作正常
2. 我尝试使用Scipy优化，但Scipy不允许创建整数变量

如何使用Python解决这个问题？我是否误解了这里的问题

更新： 上面缺少由于mean而添加的非线性组件。我将问题从total上的约束更新为mean上的约束。在一个非数学术语中，我取所有宏相乘后得到的数字的平均值，因为我希望我的平均热量小于常数N

所以从数学上来说， ∑c（m，i）*X（m，i）/X（i）<；=N（平均卡路里消耗量限制为常数N）

Answer 1

正如您已经提到的，scipy.optimize.minimize无法处理混合整数问题（MIP）。我们所能做的最多的是尝试通过惩罚方法来解决MIP，即向目标添加惩罚函数，如1.0/eps * np.sum(x*(1 - x))，其中eps > 0是给定的惩罚参数xanp.ndarray

但是，使用MIP解算器解决问题要方便得多。由于您的问题具有众所周知的背包式结构，因此您可以期望即使是非商业MIP解算器（默认情况下，纸浆使用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 += pulp.lpSum([e[i] * a[i][m] * x[i] for m in macros for i in fooditems])

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

# constraints (2)
mdl += (pulp.lpSum([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