Fast code to determine if any two subsets of columns have the same sum

Question

For a given n and m I iterate over all n by m partial circulant matrices with entries that are either 0 or 1. I want to find if there is a matrix such that there are no two subsets of the columns that give the same sum. Here when we add columns we just do it elementwise. My current code uses constraint programming via ortools. However it is not as fast I would like. For n = 7 and m = 12 it takes over 3 minutes and for n = 10, m = 18 it doesn't terminate even though there are only 2^18 = 262144 different matrices to consider. Here is my code.

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

Can this problem be solved fast enough so that n = 10, m = 18 can be solved?

Answer 1

One problem is that you are declaring the "solver" variable globally and it seems to confuse or-tools to reuse it many times. When moving it inside "isdetecting", then the (7,12) problem is solved much faster, in about 7 seconds (compared to 2:51 minutes for the original model). I haven't checked it for the larger problem, though.

Also, it might be good idea to test different labelings (instead of solver.INT_VAR_DEFAULT and solver.INT_VALUE_DEFAULT), though binary value tend to be not very sensitive to different labelings. See the code for another labeling.

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

Edit: Here are constraints to remove the all-0 solutions as mentioned in the comments. What I know of, it require a separate list. It now takes a little longer (10.4s vs 7s).

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)       

Answer 2

Something like this is what I had in mind. I'd estimate the running time for command line parameters 10 18 at less than 8 hours on my machine.

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();
    }
}