Почему я не могу установить ограниченную оптимизацию SciPy для целочисленного программирования?

Question

I've read that integer programming is either very tricky or not possible with SciPy и что мне, вероятно, нужно использовать что-то вроде zibopt для этого в Python. Но я действительно думал, что могу сделать это, создав одно ограничение «для двоичных» для каждого элемента в векторе, который оптимизируется с помощью SciPy.

Чтобы сделать это, я использовал закрывающий трюк из http://docs.python-guide.org/en/latest/writing/gotchas/#late-binding-closures и создал одну функции ограничения для каждого элемента, например:

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) 

, который печатает:

False 
True 
False 

Тогда я измененное get_binary_constraints для fmin_cobyla, ограничения которого равны "sequence of functions that all must be >=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 

который печатает следующую за тот же тест вектора [0,5, 1, 3]:

-1 
0 
-1 

Таким образом, только второе значение в массиве будет соответствовать условию> = 0.

Затем я создал очень простую задачу оптимизации следующим образом:

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

И это то, что я получаю:

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] 

Прежде чем перейти к использованию пакета R LPSolve или установить zipobt для этого, мне бы очень хотелось узнать, могу ли я просто использовать SciPy.

Я делаю что-то неправильно, или это просто невозможно сделать в SciPy?

Answer 1

Проблема в том, что, как ни странно, Integer Programming является принципиально более сложной проблемой, чем линейное программирование с действительными числами. Кто-то из потока SO, который вы связали, упоминает, что SciPy использует алгоритм Simplex. Алгоритм не работает для целочисленного программирования. Вы должны использовать другой алгоритм.

Если вы нашли способ использовать Simplex для эффективного решения целочисленного программирования, вы решили проблему P=NP, что стоит US$1,000,000вому человеку.