将 scipy.optimize.minimize 限制为整数值

Question

我正在使用 scipy.optimize.minimize 来优化一个答案只能是整数的现实问题。我当前的代码如下所示：

 from scipy.optimize import minimize

def f(x):
    return (481.79/(5+x[0]))+(412.04/(4+x[1]))+(365.54/(3+x[2]))+(375.88/(3+x[3]))+(379.75/(3+x[4]))+(632.92/(5+x[5]))+(127.89/(1+x[6]))+(835.71/(6+x[7]))+(200.21/(1+x[8]))

def con(x):
    return sum(x)-7

cons = {'type':'eq', 'fun': con}

print scipy.optimize.minimize(f, [1,1,1,1,1,1,1,0,0], constraints=cons, bounds=([0,7],[0,7],[0,7],[0,7],[0,7],[0,7],[0,7],[0,7],[0,7]))

这产生：

 x: array([  2.91950510e-16,   2.44504019e-01,   9.97850733e-01,
     1.05398840e+00,   1.07481251e+00,   2.60570253e-01,
     1.36470363e+00,   4.48527831e-02,   1.95871767e+00]

但我希望它使用整数值进行优化（将所有 x 四舍五入到最接近的整数并不总是给出最小值）。

有没有办法使用 scipy.optimize.minimize 只有整数值？

（我想我可以创建一个数组，其中包含 x 的所有可能排列，并为每个组合评估 f(x)，但这似乎不是一个非常优雅或快速的解决方案。）

原文由 nicmet 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

纸浆溶液

经过一番研究，我认为您的目标函数不是线性的。我在 Python pulp 库中重现了这个问题，但 pulp 不喜欢我们除以浮点数和“LpAffineExpression”。 这个答案 表明线性规划“不理解除法”，但该评论是在添加约束的背景下进行的，而不是目标函数。该评论将我指向“ 混合整数线性分数阶规划 (MILFP) ”和 维基百科。

如果它真的有效，你可以在 pulp 中使用以下方法（也许有人能弄清楚原因）：

 import pulp

data = [(481.79, 5), (412.04, 4), (365.54, 3)] #, (375.88, 3), (379.75, 3), (632.92, 5), (127.89, 1), (835.71, 6), (200.21, 1)]
x = pulp.LpVariable.dicts('x', range(len(data)), lowBound=0, upBound=7, cat=pulp.LpInteger)

numerator = dict((i,tup[0]) for i,tup in enumerate(data))
denom_int = dict((i,tup[1]) for i,tup in enumerate(data))

problem = pulp.LpProblem('Mixed Integer Linear Programming', sense=pulp.LpMinimize)

# objective function (doesn't work)
# TypeError: unsupported operand type(s) for /: 'float' and 'LpAffineExpression'
problem += sum([numerator[i] / (denom_int[i] + x[i]) for i in range(len(data))])

problem.solve()

for v in problem.variables():
  print(v.name, "=", v.varValue)

---

scipy.optimize 的暴力解决方案

您可以在函数中使用 brute 和 --- 的范围 slice x 如果你的函数中有 3 x slice s。 The key to all of this is to add the step size of 1 to the slice(start, stop, step ) so slice(#, #, 1) 。

 from scipy.optimize import brute
import itertools

def f(x):
  return (481.79/(5+x[0]))+(412.04/(4+x[1]))+(365.54/(3+x[2]))

ranges = (slice(0, 9, 1),) * 3
result = brute(f, ranges, disp=True, finish=None)
print(result)

---

itertools解决方案

或者您可以使用 itertools 生成所有组合：

 combinations = list(itertools.product(*[[0,1,2,3,4,5,6,7,8]]*3))

values = []
for combination in combinations:
  values.append((combination, f(combination)))

best = [c for c,v in values if v == min([v for c,v in values])]
print(best)

_注意_：出于示例目的，这是原始功能的缩小版本。

原文由 Jarad 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

可能对您的问题有帮助的一件事是：

 max([x-int(x)])=0

这不会完全解决您的问题，该算法仍会尝试作弊，您将获得具有某种程度错误的值 ~±5e-10 它仍将尝试仅通过 scipy 算法中的错误进行优化，但是聊胜于无。

 cons = ({'type':'eq', 'fun': con},
        {'type':'eq','fun': lambda x : max([x[i]-int(x[i]) for i in range(len(x))])})

在我知道解决方案的一些优化上测试了这个过程，这个过程比无约束搜索对初始值更敏感，它得到相当准确的答案但是解决方案实际上可能找不到真正的值，你基本上需要大跳跃优化过程的一部分（它用来确保它没有优化到局部最小值）来搜索样本空间，因为较小的增量通常不足以移动到下一个数字。

原文由 Simon Jones 发布，翻译遵循 CC BY-SA 3.0 许可协议