非线性约束的优化问题

Question

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

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

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

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

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

问题表述：

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

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

参数：卡路里 (C) -> 每个卡路里（宏，食物）

受约束：对于每个 m，? X (m,i) <= 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）

Answer 1

正如您已经提到的，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 += 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