2
$\begingroup$

I'm working with systems of linear equations, with a condition that all variables can have only binary values - either 0 or 1.

$$\forall x, x\in \{0;1\}$$

What I've got so far:

Say after Gaussian elimination, I'm left with this kind matrix:

$$\left[\begin{matrix} 1 & 1 & 0 &|& 1 \\ 0 & 1 & -2&|& 1 \end{matrix}\right]$$

Normally, you'd say that the Gaussian elimination failed, and that there are no unique solutions. But look at the bottom row: Since $\forall x, x\in \{0;1\}$, the only way $x_{2} - 2x_{3} = 1$ can be true is if $x_{2} = 1; x_{3} = 0$. So I can split the bottom row in two, and rewrite the matrix as:

$$\left[\begin{matrix} 1 & 1 & 0 &|& 1 \\ 0 & 1 & 0 &|& 1 \\ 0 & 0 & 1 &|& 0 \end{matrix}\right]$$

Then I Gaussian eliminate again subtracting the second row from the first, and I'm left with a fully solved matrix in reduced row echelon form:

$$\left[\begin{matrix} 1 & 0 & 0 &|& 0 \\ 0 & 1 & 0 &|& 1 \\ 0 & 0 & 1 &|& 0 \end{matrix}\right]$$

I've generalized the process as:

  1. Find the bounds that a row can take. This can be done by summing the positive coefficients to get the upper bound, and summing negative coefficients to get the lower bound.
  2. If the constant is equal to either of the bounds, rewrite the row as multiple rows, each row having a $1$ coefficient for each non-zero coefficient in the original row.
  3. If the coefficient was negative and the constant met the lower bound, or if the coefficient was positive and the constant met the upper bound, write the new row's constant as $1$. Else, write it as $0$.
  4. Repeat for all rows in the matrix.
  5. If any splits were made, re-do Gaussian elimination.

The problem:

If Gaussian elimination fails, there can be many different ways I can end up in a matrix, and I'm not guaranteed to end up with a matrix where I can apply my row splitting procedure. Even though such a matrix may be reachable, by applying some pivoting operations. For example:

$$\left[\begin{matrix} 1 & 0 & 3 & 2 &|& 5 \\ 0 & 1 & -1 & -3 &|& -1 \end{matrix}\right] \Rightarrow \left[\begin{matrix} 1 & 1 & 2 & -1 &|& 4 \\ 0 & 1 & -1 & -2 &|& -1 \end{matrix}\right] $$

Adding the second row to the first row, results in a row where the upper bound meets the constant.

So, when performing Gaussian elimination (or even after it, as a post-procedure), I should do those pivots, that result in me being in a configuration where the upper or lower bound of the row is equal to the constant. This is not easy though, since such configuration may be far away, and may require multiple pivots. I can sometimes "eyeball" it and notice them, but I don't know how to construct a formal, algorithmic description, which would lead me to said configurations.

So this is my question: How should I find the sequence of pivots needed, in order to achieve a row where the upper or lower bounds of possible values are equal to the row's constant? Any tips appreciated!

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Solving even one linear equation with $0-1$ variables is NP-complete (essentially the knapsack problem), so there is no simple way to do this in general.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .