6

整数プログラミングは非常にトリッキーであるか、SciPy では不可能で あり、おそらく Python でそれを行うには zibopt のようなものを使用する必要があることを読みました。しかし、SciPy によって最適化されているベクトルの各要素に対して 1 つの「バイナリ」制約を作成することで、それができると本当に思っていました。

そのために、 http://docs.python-guide.org/en/latest/writing/gotchas/#late-binding-closuresのクロージャー トリックを利用し、 要素ごとに 1 つの制約関数を作成しました。

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

次に、fmin_cobyla の get_binary_constraints を変更しました。この制約は、「すべてが >=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 ではこれができないのでしょうか?

4

1 に答える 1

11

問題は、直観的ではないように思われるかもしれませんが、整数計画法は実数を使用した線形計画法よりも根本的に難しい問題です。リンク先の SO スレッドの誰かが、SciPy がシンプレックスアルゴリズムを使用していると述べています。このアルゴリズムは、整数計画法では機能しません。別のアルゴリズムを使用する必要があります。

シンプレックスを使用して整数計画法を効率的に解く方法を見つけた場合、P=NP問題を解決したことになります。これは、最初に解いた人に1,000,000 米ドルの価値があります。

于 2013-04-03T17:02:39.737 に答える