Find min/max $\|x\|_{1}$ subject to $Ax = b$, using the simplex method 
Let $Ax = b$ be a linear system with $a_{i,j} \in \{0,1\}$ and $b_i \in \{0,1,2,3,4,5,6,7,8\}$. The constraints on $x$ are $x_i \in \{0,1\}$. 
  We suppose that the system admits at least one solution.  
How do I obtain the minimum and maximum amount of $1$'s in my solution
  vector?


Example:
$$\begin{bmatrix}
 1 & 1 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0\\
 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1\\
\end{bmatrix}
x = \begin{bmatrix}
 1\\
 3\\
 2\\
\end{bmatrix}$$
In this case it is quite clear that $\|x\|_{1} \geq 3$ but how do I generalize this? Apparently this can be done with the simplex algorithm. I have never done any linear programming and would appreciate an explanation of this method (maybe on the example above).
I am trying to understand the linear programming
part (page 16) of the following article: 


*

*Andrew Fowler, Andrew Young, Minesweeper: a statistical and
computational analysis, 2004.

 A: Optimal point of minimize problem is allowing as:
optimal value:3, optimal point:{x1 -> 0, x2 -> 0, x3 -> 0, x4 -> 0, x5 -> 1, x6 -> 0, x7 -> 0, x8 -> 0, x9 -> 1, x10 -> 1, x11 -> 0, x12 -> 0}
Optimal point of maximize problem is allowing as:
optimal value:4, optimal point:{x1 -> 0, x2 -> 0, x3 -> 0, x4 -> 0, x5 -> 0, x6 -> 0, x7 -> 1, x8 -> 0, x9 -> 1, x10 -> 0, x11 -> 1, x12 -> 1}
Above problem is a kind of pure binary linear programming problem.
I have new and good algorithm and software to solve this problem.
A: Given an underdetermined linear system $\mathrm A \mathrm x = \mathrm b$ in $\mathrm x \in \{0,1\}^n$, we would like to extremize the number of ones in the solution. Since $x_i \in \{0,1\}$, there is no need to extremize $\|\mathrm x\|_1$. Instead, we extremize $1_n^T \mathrm x$. We then have the binary program
$$\begin{array}{ll} \text{extremize} & 1_n^T \mathrm x\\ \text{subject to} & \mathrm A \mathrm x = \mathrm b\\ & \mathrm x \in \{0,1\}^{n}\end{array}$$
which can be rewritten as an integer program (IP)
$$\begin{array}{ll} \text{extremize} & 1^T \mathrm x\\ \text{subject to} & \mathrm A \mathrm x = \mathrm b\\ & 0_n \leq \mathrm x \leq 1_n\\ & \mathrm x \in \mathbb Z^n\end{array}$$
Relaxing the integrality constraint, we then have a linear program (LP)
$$\begin{array}{ll} \text{extremize} & 1^T \mathrm x\\ \text{subject to} & \mathrm A \mathrm x = \mathrm b\\ & 0_n \leq \mathrm x \leq 1_n\\ & \mathrm x \in \mathbb R^n\end{array}$$
which can be solved using, say, the simplex method. Of course, there is no guarantee that the solution to the LP is the same as the solution to the IP.
