¿Por qué no puedo manipular la optimización restringida de SciPy para la progtwigción de enteros?

He leído que la progtwigción de enteros es muy difícil o no es posible con SciPy y que probablemente necesito usar algo como zibopt para hacerlo en Python. Pero realmente pensé que podría hacerlo creando una restricción “es binaria” para cada elemento en un vector optimizado por SciPy.

Para hacer eso, utilicé el truco de cierre de http://docs.python-guide.org/en/latest/writing/gotchas/#late-binding-closures y creé una función de restricción para cada elemento, así:

def get_binary_constraints(vector, indices_to_make_binary=None): indices_to_make_binary = indices_to_make_binary or range(len(vector)) for i in indices_to_make_binary: def ith_element_is_binary(vector, index=i): return vector[index] == 0 or vector[index] == 1 yield ith_element_is_binary test_vector = scipy.array([0.5, 1, 3]) constraints = list(get_binary_constraints(test_vector)) for constraint in constraints: print constraint(test_vector) 

que imprime:

 False True False 

Luego modifiqué get_binary_constraints para fmin_cobyla, cuyas restricciones son una “secuencia de funciones que todas deben ser> = 0” .

 def get_binary_constraints(vector, indices_to_make_binary=None): indices_to_make_binary = indices_to_make_binary or range(len(vector)) for i in indices_to_make_binary: def ith_element_is_binary(vector, index=i): return int(vector[index] == 0 or vector[index] == 1) - 1 yield ith_element_is_binary 

que imprime lo siguiente para el mismo vector de prueba [0.5, 1, 3]:

 -1 0 -1 

Por lo tanto, solo el segundo valor de la matriz cumplirá la condición> = 0.

Luego, configuré un problema de optimización muy simple de la siguiente manera:

 from scipy import optimize import scipy def get_binary_constraints(vector, indices_to_make_binary=None): indices_to_make_binary = indices_to_make_binary or range(len(vector)) for i in indices_to_make_binary: def ith_element_is_binary(vector, index=i): return int(vector[index] == 0 or vector[index] == 1) - 1 yield ith_element_is_binary def objective_function(vector): return scipy.sum(vector) def main(): guess_vector = scipy.zeros(3) constraints = list(get_binary_constraints(guess_vector)) result = optimize.fmin_cobyla(objective_function, guess_vector, constraints) print result if __name__ == '__main__': main() 

Y esto es lo que obtengo:

 Return from subroutine COBYLA because the MAXFUN limit has been reached. NFVALS = 1000 F =-8.614066E+02 MAXCV = 1.000000E+00 X =-2.863657E+02 -2.875204E+02 -2.875204E+02 [-286.36573349 -287.52043407 -287.52043407] 

Antes de usar el paquete LPSolve de R o instalar zipobt para esto, realmente me gustaría ver si puedo usar SciPy.

¿Estoy haciendo algo mal o simplemente no es posible hacerlo en SciPy?

El problema es que, por muy poco intuitivo que parezca, la Progtwigción Integral es un problema fundamentalmente más difícil que la Progtwigción Lineal con números reales. Alguien en el subproceso de SO que has vinculado menciona que SciPy usa el algoritmo Simplex . El algoritmo no funciona para la progtwigción de enteros. Tienes que usar un algoritmo diferente.

Si encuentra una manera de usar Simplex para resolver la progtwigción de enteros de manera eficiente, ha resuelto el problema P = NP , que tiene un valor de US $ 1,000,000 para la primera persona a resolver.