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.
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.