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


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

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

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

1 6

1 ответ:

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

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