Почему я не могу использовать ограниченную оптимизацию 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 ответ:
Проблема заключается в том, что, как бы неинтуитивно это ни казалось, целочисленное Программирование является принципиально более сложной задачей, чем линейное программирование с вещественными числами. Кто-то в потоке SO, с которым вы связались, упоминает, что SciPy использует Симплексный алгоритм . Алгоритм не работает для целочисленного программирования. Вы должны использовать другой алгоритм.
Если вы нашли способ эффективно использовать Симплекс для решения задач целочисленного программирования, вы решили задачу P=NP , который стоит US$1,000,000 первому человеку, чтобы решить.