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

Question

Я читал, что целочисленное программирование либо очень сложно, либо невозможно с SciPy, и что мне, вероятно, нужно использовать что-то вроде zibopt, чтобы сделать это в Python. Но я действительно думал, что смогу сделать это, создав одно ограничение "является двоичным" для каждого элемента в векторе, оптимизируемом SciPy.

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

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, чьи ограничения представляют собой "последовательность функций, у которых все должно быть> = 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

Таким образом, только 2-е значение в массиве будет соответствовать условию>= 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]

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

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

Answer 1

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

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