2
$\begingroup$

I'm searching for an integer solution to an arbitrary set of linear equations with binary coefficients. It is given that the rank of the Matrix is not maximal. The right hand side is the 0-vector.

So let $A \in \{0,1\}^{(d+k)\cdot (d+1)}$ with last column fixed to 1: $A_{i,d+1}=1\forall i\in \{1,..,d+k\}$, with $k \in \mathbb{N} \cup\{0\}$

Let $x\in \mathbb{Z}^{d+1}$ and $r = (0,...,0)^t \in \mathbb{N}^{d+k}$.

It is given that $rank(A) =d$ and there are no conflicting linear equations, thus there are infinitively many solutions.

I now want to search only for non-trivial integer solutions of $ A \cdot x =r$, preferably, the integers should be small.

Let's put that in the way that $x^* = argmin_x (max_i |x_i|)$ s.t. $Ax=r$ and $x\neq 0$. If it's easier for the task, the use of maximum-norm is not necessary, but the requirement that the integers of the solution should be near 0 (in the common sense, i.e. all above 10 would be odd to my kind of problem), is non-optional.

Are there fast/efficient algorithms to achieve this?

  • 0
    $x \in N^{d+1} or Z^{d+1}$ ? or is the addition mod 2 ?2012-06-15
  • 0
    your right, should be $\mathbb{Z}$, just corrected it. Thank you!2012-06-15
  • 0
    actually, in the case of my matrices, I currently think that x is in ${-1,0,1}^{d+1}$, but since i'm not sure about that, I asked that more general problem.2012-06-15
  • 0
    als, what is the purpose of $x_{*}$ you just defined it and didnt do anything wih it2012-06-15
  • 0
    $x^*$ is short for "optimal solution"2012-06-15
  • 0
    okay,this problem seems to be NP hard to me (we can reduce SAT to this problem).so ,we can't expect it to have a deterministic poly time algo.2012-06-15
  • 0
    Fair enough, but do you see a good heuristic? The use of a strict norm isn't really necessary, i just added it to emphasise the goal2012-06-15
  • 0
    i didn't consider the norm at all.2012-06-15
  • 0
    i am sorry, i was mistaken about reduction.2012-06-15
  • 0
    and btw is it the last row or last column?2012-06-15
  • 0
    It's the last column, such that the last entry of x is in every equation. (basically, $-x_{d+1}$ is an unknown right hand side to a set of linear equations without that last column)2012-06-15
  • 0
    @st0ne I don't necessarily think you are wrong about NP-hardness. Monotone exactly 1-in-3 SAT has a very similar integer programming formulation to the OP's question.2013-01-04

0 Answers 0