将 scipy.optimize.minimize 限制为整数值 [英] Restrict scipy.optimize.minimize to integer values

问题描述

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

I'm using scipy.optimize.minimize to optimize a real-world problem for which the answers can only be integers. My current code looks like this:

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 舍入到最接近的整数并不总是给出最小值).

But I want it optimized with integer values (rounding all x to the nearest whole number doesn't always give the minimum).

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

Is there a way to use scipy.optimize.minimize with only integer values?

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

(I guess I could create an array with all possible permutations of x and evaluate f(x) for each combination, but that doesn't seem like a very elegant or quick solution.)

推荐答案

纸浆解决方案

经过一些研究，我认为您的目标函数不是线性的.我在 Python pulp 库中重新创建了这个问题，但纸浆不喜欢我们除以一个浮点数和LpAffineExpression".这个答案表明线性规划不理解除法"，但该评论是在添加约束的上下文中，而不是目标功能.该评论将我指向混合整数线性分数规划 (MILFP)" 和 维基百科.

After some research, I don't think your objective function is linear. I recreated the problem in the Python pulp library but pulp doesn't like that we're dividing by a float and 'LpAffineExpression'. This answer suggests that linear programming "doesn't understand divisions" but that comment is in context of adding constraints, not the objective function. That comment pointed me to "Mixed Integer Linear Fractional Programming (MILFP)" and on Wikipedia.

如果它确实有效，您可以通过以下方式在纸浆中进行操作(也许有人可以找出原因):

Here's how you could do it in pulp if it actually worked (maybe someone can figure out why):

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).

You can use brute and ranges of slices for each x in your function. If you have 3 xs in your function, you'll also have 3 slices in your ranges tuple. 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 生成所有组合:

Or you can use itertools to generate all combinations:

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)

注意:这是用于示例目的的原始函数的缩小版本.

Note: this is a scaled-down version of your original function for example purposes.

这篇关于将 scipy.optimize.minimize 限制为整数值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！