Restrinja scipy.optimize.minimize a valores enteros

Estoy usando scipy.optimize.minimize para optimizar un problema del mundo real para el que las respuestas solo pueden ser enteros. Mi código actual se ve así:

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

Esto produce:

 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] 

Pero quiero que se optimice con valores enteros (redondear todo x al número entero más cercano no siempre da el mínimo).

¿Hay una manera de usar scipy.optimize.minimize con solo valores enteros?

(Supongo que podría crear una matriz con todas las permutaciones posibles de x y evaluar f (x) para cada combinación, pero eso no parece ser una solución muy elegante o rápida).

solución de pulpa

Después de algunas investigaciones, no creo que su función objective sea lineal. Volví a crear el problema en la biblioteca de pulpa de Python , pero a Pulp no le gusta que estemos dividiendo por un flotador y ‘LpAffineExpression’. Esta respuesta sugiere que la progtwigción lineal “no comprende las divisiones”, pero ese comentario está en el contexto de agregar restricciones, no la función objective. Ese comentario me señaló ” Progtwigción fraccional lineal de enteros mixtos (MILFP) ” y en Wikipedia .

A continuación le indicamos cómo podría hacerlo en pulpa si realmente funcionara (quizás alguien pueda averiguar por qué):

 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) 

solución bruta con scipy.optimize

Puede usar brute y rangos de slice para cada x en su función. Si tiene 3 x s en su función, también tendrá 3 slice en la tupla de rangos. La clave de todo esto es agregar el tamaño de paso de 1 a la slice(start, stop, step ) así que 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) 

solución de itertools

O puedes usar itertools para generar todas las combinaciones:

 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) 

Nota : esta es una versión reducida de su función original por ejemplo.

Una cosa que podría ayudar a su problema podría tener una restricción como:

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

Esto no va a resolver completamente su problema, el algoritmo aún intentará hacer trampa y obtendrá valores con cierto nivel de error ~±5e-10 que aún intentará y optimizará solo por el error en el algoritmo de scipy, pero es mejor que nada

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

después de haber probado este proceso en algunas optimizaciones que conozco, este proceso es más sensible a los valores iniciales que a la búsqueda sin restricciones, obtiene respuestas bastante precisas, sin embargo, la solución puede no encontrar el verdadero valor, básicamente se requiere un gran salto. del proceso de optimización (lo que usa para asegurarse de que no se está optimizando a un mínimo local) para buscar el espacio de muestra, ya que los incrementos más pequeños generalmente no son lo suficientemente fuertes como para pasar al siguiente número.

Función genérica para solución de fuerza bruta. Hace un poco mejor trabajo que Brute en scipy, ya que scipy en realidad ejecuta una función con números flotantes, no solo enteros, aunque el rango lo dice explícitamente, como Jarad declaró

 def brute(func, arg_ranges, finish=min): if isinstance(arg_ranges, dict): args = {k:np.unique(np.hstack([a for r in rs for a in r]) if isinstance(rs, list) else [a for a in rs]) for k,rs in arg_ranges.items()} print(args) return finish([(dict(zip(args.keys(), vs)), func(**dict(zip(args.keys(), vs)))) for vs in itertools.product(*args.values())], key=lambda x: x[1]) elif isinstance(arg_ranges, list): return finish([(i, func(i)) for r in arg_ranges for i in r], key=lambda x: x[1]) else: return finish([(i, func(i)) for i in arg_ranges], key=lambda x: x[1]) print(brute(lambda x,y: x / (y + 2), {'x':[range(1,5,2), range(0,6,1)], 'y':range(2,5,1)}))