Can this be expressed using Integer Programming or Constraint Programming?

Question

Consider a fixed m by n matrix M, all of whose entries are 0 or 1. The question is whether there exists a non zero vector v, all of whose entries are -1, 0 or 1 for which Mv = 0. For example,

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

In this example, there is no such vector v.

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

In this example, the vector (0,0,0,1) gives M_2v = 0.

I am currently solving this problem by trying all different vectors v.

However, is it possible to express the problem as an integer programming problem or constraint programming problem so I can use an existing software package, such as SCIP instead which might be more efficient.

@Cptn_Hammer What is the confusion? Vectors can in general contain any numerical values. I just restrict them to -1, 0 and 1 in this case. — Simd
– Simd, Commented Jul 9, 2015 at 18:27
"Consider a fixed m by n matrix M, all of whose entries are 0 or 1." Should this say -1, 0, or 1? — ale10ander
– ale10ander, Commented Jul 9, 2015 at 20:29
@Cptn_Hammer No. The vector takes different values from the matrix. — Simd
– Simd, Commented Jul 9, 2015 at 20:57
Sounds like you need a tutorial on some linear algebra concepts, like "null space", "singular value decomposition", "homogenous linear equations", etc... — twalberg
– twalberg, Commented Jul 9, 2015 at 21:23
@twalberg The restrictions of the vectors in the null space to a lattice makes it all a little trickier than that I think. — Simd
– Simd, Commented Jul 9, 2015 at 21:24

hakank · Accepted Answer · 2015-07-09 19:04:00Z

4

It would help a little if you also give a positive example, not just a negative.

I might have missed something in the requirement/definitions, but here is a way of doing it in the Constraint Programming (CP) system MiniZinc (http://minizinc.org/). It don't use any specific constraints unique to CP systems - except perhaps for the function syntax, so it should be possible to translate it to other CP or IP systems.

% 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
   ];

By changing the definition of "M" to use decision variables with the domain 0..1 instead of constants:

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

then this model yield 18066 different solutions, for example these two:

  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

Note: Generating all solutions is probably more common in CP systems than in traditional MIP systems (this is a feature that I really appreciate).

answered Jul 9, 2015 at 19:04

hakank

6,8641 gold badge20 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Simd Over a year ago

Thank you for this. I also added a positive example.

hakank Over a year ago

For the positive example you added, the model yield two solutions: v=[0,0,0,-1] and v=[0,0,0,1]. Is this correct according to your description?

Collectives™ on Stack Overflow

Can this be expressed using Integer Programming or Constraint Programming?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related