Variable reduction in a Linear Programming problem

Question

I am currently working on a problem where I need to find a feasible solution to linear equality constraints.

$\hspace{50mm}Ax=b,$
$\hspace{50mm}x\geq0,$

$\hspace{38mm}$where $A \in R^{m*n}, b\in R^m, A_{ij} \in \{0,1\}$
$ \hspace{50mm}m << n$

The number of variables is greater than the number of constraints in orders of magnitude.
The simplex method gives Basic Feasible Solution(BFS) in which most (at least n-m) variables are zero. I wanted to know if we can preprocess the constraints so that we can get a reduction in the number of variables in O(n) (order of the number of variables).

Note: I am fine with approximate solutions as long as the error is bounded.

Answer 1

Linear programming presolvers perform a variety of techniques to simplify the problem before invoking the main LP algorithm. For example, eliminate variables that must be 0 in every feasible solution, or remove redundant constraints. Here are a few that might apply to your problem:

1. If some constraint $i$ has only one $A_{i,j}=1$, then $x_j=b$, and you can remove that variable and constraint from the problem.
2. You can set upper bounds $x_j \le \min\{b_i: A_{i,j}=1\}$.
3. If $b_i<0$ for some $i$, the problem is infeasible.
4. If $b_i=0$ for some $i$, then $x_j=0$ for all $j$ with $A_{i,j}=1$. You can then remove those variables and that constraint from the problem.
5. If some set of constraints is linearly dependent, you can omit one of them.

Typically, presolvers apply these techniques multiple times until nothing changes or until some iteration limit is reached.