将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

一件事可能会帮助您解决问题，您可能会受到以下限制：

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))])})

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

Answer 2

以下是使用Python Gekko （我维护的一个包）解决混合整数非线性规划问题的方法：

from gekko import GEKKO

m = GEKKO(remote=False)
x = m.Array(m.Var,9,lb=0,ub=7,integer=True)

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

m.Minimize(f(x))
m.Equation(sum(x)==7)
m.options.SOLVER=1
m.solve()
print(x)

这给出了解决方案：

 ---------------------------------------------------
 Solver         :  APOPT (v1.0)
 Solution time  :  0.0529 sec
 Objective      :  859.5269999999999
 Successful solution
 ---------------------------------------------------


[[0.0] [0.0] [1.0] [1.0] [1.0] [0.0] [1.0] [0.0] [3.0]]

Answer 3

纸浆溶液

经过研究，我认为您的目标函数不是线性的。我在Python 纸浆库中重新创建了问题，但纸浆不喜欢我们用浮点数和'LpAffineExpression'进行划分。这个答案表明线性编程“不理解除法”，但是注释是在添加约束而不是目标函数的情况下进行的。该评论将我指向“ 混合整数线性分数规划（MILFP） ”和Wikipedia上。

如果纸浆实际起作用，可以按照以下方法进行处理（也许有人可以弄清楚原因）：

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和的范围。如果函数中有3 s，则范围元组中也有3 s。所有这一切的关键是添加步的尺寸为如此。slicexxslice1slice(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)

注意：这是原始功能的缩小版本，仅供参考。