python - 将 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)，但这似乎不是一个非常优雅或快速的解决方案。)

Answer 1

PuLP 溶液

经过一些研究，我认为您的目标函数不是线性的。我在 Python 中重新创建了问题 pulp库，但 PuLP 不喜欢我们除以 float 和“LpAffineExpression”。 This answer表明线性规划“不理解除法”，但该评论是在添加约束的背景下进行的，而不是目标函数。该评论将我指向“Mixed Integer Linear Fractional Programming (MILFP)”和Wikipedia .

如果它确实有效，您可以在 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 的暴力解决方案

您可以对函数中的每个 x 使用 brute 和 slice 范围。如果您的函数中有 3 个 x，那么您的范围元组中也会有 3 个 slice。所有这一切的关键是将 1 的 step 大小添加到 slice(start, stop,step ) 所以 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)

注意:出于示例目的，这是原始函数的缩小版本。