How to make an underdetermined and infeasible system Ax=b, x>=0,b>=0 feasible?

Question

I want to make the system of linear equations feasible,

$Ax = b$

1. The system is under-determined
2. Matrix $A$ is a binary matrix
3. Vector $x$ is non-negative
4. Vector $b$ has non negative values
5. vector $b$ has values from experimental measurements which could be erroneous yielding infeasible system.
6. Its a large system, number of equations could are of the order $100$ and number of variables are of the order $500$.

I have a way of solving it by adding elastic constraints to each equations and then minimize sum of all the elastic constraints subjected to the elastisized constraints. The short illustration is given below:

$$\begin{cases}a_1 + a_2 + a_3 = 10 \\a_1 = 20\\a_1,a_2,a_3\geq 0\end{cases}$$

The above system has no feasible solution.

One way to make it feasible is the following LP formulation:

minimize: $e_1 + e_2 + e_3 + e_4$ s.t.

$$\begin{cases}a_1 + a_2 + a_3 + e_1 - e_2 = 10\\a_1 + e_3 - e_4= 20\\a_1,a_2,a_3,e_1,e_2,e_3,e_4\geq 0\end{cases}$$

Now after solving the system one could put the values of $e_1,e_2,e_3,e_4$ and adjust the right hand side (rhs) values. That system would be a feasible system.

This works well but the problem is that shift in the rhs values are not necessarily uniform. It could be that most of the elastic variables are $0$ and only few of them are non-zero since our objective function is simply sum of all the elastic variables.

Q1. Could you suggest a better objective function so that the change in rhs values is more uniform over all the linear equations?

Q2. Any other suggestions or methodology to make the under-determined system Ax=b feasible ?

Thank you in advance.

Answer 1

I think what you call "adding elastic constraint to an equation" is usually called "adding a slack variable (or pair of slacks) to an equation".

You can add a single (free) slack variable $s_i$ to an equation $i$ (instead of a pair of positive slacks) and then minimize the sum of squares: $$\min \sum_i s_i^2$$ (many solvers can handle convex quadratic objectives). This will also put a larger penalty on large slacks, so distributing the pain more evenly. Essentially we are doing here non-negative least squares.

To prevent large slacks (and thus distribute them more evenly) but keep the model linear can be done as follows. Instead of minimizing the sum of the slacks, minimize the maximum of the slacks. I.e. $$\begin{align}\min\>& t\\&e_i \le t\end{align}$$