将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 纸浆库中重新创建了问题，但纸浆不喜欢我们将其除以浮点数和"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屋！