Быстрый код, чтобы определить, имеют ли какие-либо два подмножества столбцов одинаковую сумму

Одна из проблем заключается в том, что вы объявляете переменную «решателя» глобально, и это, кажется, сбивает с толку инструменты or, чтобы повторно использовать ее много раз. Когда он перемещается внутрь «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

Изменить: вот ограничения для удаления решений all-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)       

Примерно это то, что я имел в виду. Я бы оценил время работы параметров командной строки 10 18 на моей машине менее 8 часов.

public class Search {
    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        int m = Integer.parseInt(args[1]);
        int row = search(n, m);
        if (row >= 0) {
            printRow(m, row);
        }
    }

    private static int search(int n, int m) {
        if (n < 0 || m < n || m >= 31 || powOverflows(m + 1, n)) {
            throw new IllegalArgumentException();
        }
        long[] column = new long[m];
        long[] sums = new long[1 << m];
        int row = 1 << m;
        while (row-- > 0) {
            System.err.println(row);
            for (int j = 0; j < m; j++) {
                column[j] = 0;
                for (int i = 0; i < n; i++) {
                    column[j] = (column[j] * (m + 1)) + ((row >> ((i + j) % m)) & 1);
                }
            }
            for (int subset = 0; subset < (1 << m); subset++) {
                long sum = 0;
                for (int j = 0; j < m; j++) {
                    if (((subset >> j) & 1) == 1) {
                        sum += column[j];
                    }
                }
                sums[subset] = sum;
            }
            java.util.Arrays.sort(sums);
            boolean duplicate = false;
            for (int k = 1; k < (1 << m); k++) {
                if (sums[k - 1] == sums[k]) {
                    duplicate = true;
                    break;
                }
            }
            if (!duplicate) {
                break;
            }
        }
        return row;
    }

    private static boolean powOverflows(long b, int e) {
        if (b <= 0 || e < 0) {
            throw new IllegalArgumentException();
        }
        if (e == 0) {
            return false;
        }
        long max = Long.MAX_VALUE;
        while (e > 1) {
            if (b > Integer.MAX_VALUE) {
                return true;
            }
            if ((e & 1) == 1) {
                max /= b;
            }
            b *= b;
            e >>= 1;
        }
        return b > max;
    }

    private static void printRow(int m, int row) {
        for (int j = 0; j < m; j++) {
            System.out.print((row >> j) & 1);
        }
        System.out.println();
    }
}