在 or 工具中对方差-协方差矩阵计算进行建模

Question

我的任务是将 Excel 求解器解决方案自动化到我们的应用程序中。我遇到了or-tools，它似乎接近我想要的 - 尽管我不确定，因为这是我第一次尝试与SAT相关的问题空间。

我有大约 30 个约束和 1 个目标。幸运的是，我能够将所有约束建模为 or-tools，但添加目标会不断返回Not an integer linear expression错误。我试图最小化的计算是一个方差-协方差矩阵：

#!/usr/bin/env python3
from __future__ import print_function
from ortools.sat.python import cp_model
model = cp_model.CpModel()
weights = [0] * 14 # 14 different weights optimize on
values = [...] # Values corresponding to the weights
varcovmat = [[...],[...],[...], ...] # Square Matrix, 14x14
for i in range(0, len(weights)):
weights[i] = model.NewIntVar(0, 10000, 'w'+str(i))
# Add some constraints
model.Add(cp_model.LinearExpr.Sum(weights) == 10000)
model.Add(cp_model.LinearExpr.ScalProd(weights, values) == 2000000)
# Add the Objective
expressions = [0]*len(cov)
for i in range(0, len(cov)):
expressions[i] = sum([y*x for x,y in zip(weights, [int(x[i]*100) for x in cov])])
model.Minimize(sum([weights[i] * expressions[i] for i in range(0, len(cov))])) # Here is where the error is thrown

运行此程序，将抛出以下内容：

TypeError: Not an integer linear expression: (((((((((((((((100 * w0)) + (36 * w1)) + (5 * w2)) + (30 * w3)) + (-14 * w4)) + (12 * w5)) + (-8 * w6)) + (10 * w7)) + -w8) + (-15 * w9)) + (-13 * w10)) + (-13 * w11)) + (-11 * w12)) + (-6 * w13))

这是我可以使用的问题类型或工具来解决吗？我知道如果我省略目标，我可以搜索所有解决方案并选择获胜的解决方案，但这是一种相当长/繁琐的方法。

有没有办法将这个问题正确地建模为 or-tools，或者我应该关注 or 工具的不同功能？

任何指导/帮助将不胜感激！

我尝试过的其他变体和错误输出：

# Add the Objective
expressions = [0]*len(cov)
for i in range(0, len(cov)):
expressions[i] = cp_model.LinearExpr.ScalProd(weights, [int(x[i]*100) for x in cov])
model.Minimize(cp_model.LinearExpr.ScalProd(weights, expressions))

TypeError: Not an integer: 100 * w0 + 36 * w1 + 5 * w2 + 30 * w3 - 14 * w4 + 12 * w5 - 8 * w6 + 10 * w7 - w8 - 15 * w9 - 13 * w10 - 13 * w11 - 11 * w12 - 6 * w13

Answer 1

多亏了Erwin的评论，事实证明or-tools不是适合这项工作的工具 - 使用scipy.optimize.minimize取得了成功。不幸的是，CVXPY不喜欢输入 - 猜测值不再使其成为凸优化问题。