linear equations with boundary conditions When solving a system of linear equations I want to introduce "boundary conditions" (not sure if that's the right term) to the values of the variables. Each variable must be a non-negative integer and has a maximum value.
Here is an example of such a problem;
\begin{array}{|c|c|c|c|c|c|c|}
\hline
a & b & c & d & e & f \\ \hline
1 & 0 & 0 & 0 & 0 & 1 & 1 \\ \hline
0 & 1 & 0 & 0 & 1 & 0 & 1 \\ \hline
0 & 0 & 1 & 0 & 1 & 1 & 2 \\ \hline
0 & 0 & 0 & 1 &-1 &-1 &-1 \\ \hline
\end{array}
The system of equations is already transformed to reduced echelon form.
The given maximum values for variables a to f are as following;
\begin{array}{|c|c|c|c|c|c|}
\hline
a & b & c & d & e & f \\ \hline
1 & 2 & 2 & 1 & 1 & 1 \\ \hline
\end{array}
Another condition is that the sum of all variables is a constant, in the case of the example it is 3. This is easily achieved by adding the row "1 1 1 1 1 1 3" (which is already a linear combination of other rows so doesn't add anything).
Without the boundary conditions the trivial solution would be 1 1 2 -1 0 0 but since negative values are not allowed this solution is not valid.
With the given conditions the possible solution are;
\begin{array}{|c|c|c|c|c|c|}
\hline
a & b & c & d & e & f \\ \hline
0 & 0 & 0 & 1 & 1 & 1 \\ \hline
0 & 1 & 1 & 0 & 0 & 1 \\ \hline
1 & 0 & 1 & 0 & 1 & 0 \\ \hline
\end{array}
Is there any way of solving this problem in polynomial time complexity? It is not possible to introduce the conditions by adding extra rows to the system of linear equations, right?
Eventually I want to solve systems with up to 40 variables.
I preferable want to list all possible solutions but determining whether or not a valid solution exists without brute-forcing all possibilities would also be nice.
 A: Your question is related to integer programming (maximize $c^Tx$ subject to $Ax\leq b$ and $x_i\in\mathbb{Z}$). To get constraints like $Ax=b$ you can do $Ax\leq b$ and $-Ax\leq -b$ and to get constraints like $x_i\geq 0$ you can do $-Ix\leq 0$.
Your problem is about finding feasible points for the optimization problem above; i.e. you don't care about the value of $c^Tx$.
In general, integer programming is NP-complete. Similarly, the task of finding all feasible points cannot be done in polynomial time because there could be exponentially many feasible points. I am unsure about the time complexity of finding a single point.
A general technique for solving integer programs is to first solve the linear program (same problem without integer constraints) and then round it. However, this doesn't always gives the best solution, or guarantee that the rounded point is in your region. There are also plenty of software packages for integer and linear programming, so it might also be worth just seeing if those work out of the box for your needs.
Finally, if your equations have some additional structure, then it might be possible to solve this specific class of problems more efficiently.
