1

与えられた n と mに対して、エントリが 0 または 1の n × m 部分巡回行列すべてを反復処理します。同じ合計を与える列のサブセットが 2 つ存在しないような行列があるかどうかを調べたいと思います。ここで列を追加するときは、要素ごとに行います。私の現在のコードはortools による制約プログラミングを使用しています。しかし、それは私が望むほど速くはありません。n = 7 および m = 12 の場合は 3 分以上かかり、n = 10、m = 18 の場合は、考慮すべき異なる行列が 2^18 = 262144 しかないにもかかわらず終了しません。これが私のコードです。

from scipy.linalg import circulant
import numpy as np
import itertools
from ortools.constraint_solver import pywrapcp as cs

n = 7
m = 12

def isdetecting(matrix):
    X = np.array([solver.IntVar(values) for i in range(matrix.shape[1])])
    X1 = X.tolist()
    for row in matrix:
        x = X[row].tolist()
        solver.Add(solver.Sum(x) == 0)
    db = solver.Phase(X1, solver.INT_VAR_DEFAULT, solver.INT_VALUE_DEFAULT)
    solver.NewSearch(db)
    count = 0
    while (solver.NextSolution() and count < 2):
        solution = [x.Value() for x in X1]
        count += 1
    solver.EndSearch()
    if (count < 2):
        return True

values = [-1,0,1]
solver = cs.Solver("scip")

for row in itertools.product([0,1],repeat = m):
    M = np.array(circulant(row)[0:n], dtype=bool)
    if isdetecting(M):
        print M.astype(int)
        break

n = 10、m = 18 を解くことができるように、この問題を十分速く解くことができますか?

4

2 に答える 2

2

1 つの問題は、「ソルバー」変数をグローバルに宣言していて、それを何度も再利用するために or-tools を混乱させているように見えることです。それを「isdetecting」内に移動すると、(7,12) 問題ははるかに速く、約 7 秒で解決されます (元のモデルの 2:51 分と比較して)。ただし、より大きな問題については確認していません。

また、(solver.INT_VAR_DEFAULT と solver.INT_VALUE_DEFAULT の代わりに) さまざまなラベル付けをテストすることをお勧めしますが、バイナリ値はさまざまなラベル付けにあまり敏感ではない傾向があります。別のラベル付けのコードを参照してください。

def isdetecting(matrix):
   solver = cs.Solver("scip") # <----
   X = np.array([solver.IntVar(values) for i in range(matrix.shape[1])])
   X1 = X.tolist()
   for row in matrix:
       x = X[row].tolist()
       solver.Add(solver.Sum(x) == 0)
   # db = solver.Phase(X1, solver.INT_VAR_DEFAULT, solver.INT_VALUE_DEFAULT)
   db = solver.Phase(X1, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_CENTER_VALUE)    
   solver.NewSearch(db)
   count = 0
   while (solver.NextSolution() and count < 2):
       solution = [x.Value() for x in X1]
       count += 1
   solver.EndSearch()
   if (count < 2):
       print "FOUND"
       return True

編集：コメントに記載されているように、すべて0のソリューションを削除するための制約があります。私が知っていることは、別のリストが必要です。少し時間がかかります (10.4 秒対 7 秒)。

X1Abs = [solver.IntVar(values, 'X1Abs[%i]' % i) for i in range(X1_len)]
for i in range(X1_len):
    solver.Add(X1Abs[i] == abs(X1[i])) 
solver.Add(solver.Sum(X1Abs) > 0)
于 2014-03-04T17:34:38.827 に答える