2

考虑一个固定的 m × n 矩阵 M，其所有元素为 0 或 1。问题是是否存在一个非零向量 v，其所有元素为 -1、0 或 1，其中 Mv = 0。例如，

      [0 1 1 1]
M_1 = [1 0 1 1]
      [1 1 0 1]

在这个例子中，没有这样的向量 v。

      [1 0 0 0]
M_2 = [0 1 0 0]
      [0 0 1 0]

在此示例中，向量 (0,0,0,1) 给出 M_2v = 0。

我目前正在通过尝试所有不同的向量 v 来解决这个问题。

但是，是否可以将问题表示为整数规划问题或约束规划问题，以便我可以使用现有的软件包，例如 SCIP，这可能更有效。

4

1 回答 1

4

如果你也举一个正面的例子，而不仅仅是一个负面的例子，这会有所帮助。

我可能错过了需求/定义中的某些内容，但这是在约束编程 (CP) 系统 MiniZinc ( http://minizinc.org/ ) 中执行此操作的一种方法。它不使用 CP 系统特有的任何特定约束——可能除了函数语法之外，因此应该可以将其转换为其他 CP 或 IP 系统。

% dimensions
int: rows = 3;
int: cols = 4;
% the matrix
array[1..rows, 1..cols] of int: M = array2d(1..rows,1..cols, 
    [0, 1, 1, 1,
     1, 0, 1, 1,
     1, 1, 0, 1,
     ] );

 % function for matrix multiplication: res = matrix x vec 
 function array[int] of var int: matrix_mult(array[int,int] of var int: m, 
                                             array[int] of var int: v) =
    let {
       array[index_set_2of2(m)] of var int: res; % result
       constraint
       forall(i in index_set_1of2(m)) (
           res[i] = sum(j in index_set_2of2(m)) (
               m[i,j]*v[j]
           )
       )
     ;
    } in res; % return value

   solve satisfy;
   constraint
       % M x v = 0
       matrix_mult(M, v) = [0 | j in 1..cols] /\
       sum(i in 1..cols) (abs(v[i])) != 0 % non-zero vector
   ;
   output 
   [
       "v: ", show(v), "\n",
       "M: ", 
   ]
   ++
   [
     if j = 1 then "\n" else " " endif ++
       show(M[i,j])
     | i in 1..rows, j in 1..cols
   ];

通过更改“M”的定义以使用域为 0..1 的决策变量而不是常量：

  array[1..rows, 1..cols] of var 0..1: M;

那么这个模型产生 18066 个不同的解决方案，例如这两个：

  v: [-1, 1, 1, 1]
  M: 
   1 0 0 1
   1 1 0 0
   1 0 0 1
  ----------
  v: [-1, 1, 1, 1]
  M: 
  0 0 0 0
  1 0 1 0
  1 0 0 1

注意：在 CP 系统中生成所有解决方案可能比在传统 MIP 系统中更常见（这是我非常欣赏的一个功能）。

于 2015-07-09T19:04:00.563 回答