In a LP problem Ax = b, how to solve for A instead of x?

Question

I have a multi-objective linear programming problem of the form Ax = b, where A is a matrix and x and b are vectors. x is known, and I'm looking to minimise each row of b by solving for A.

Constraints are:

1. Each column of A must add up to 1.

2. A will start with some values being 0, and those must remain 0. In other words, A is sparse.

I know of algorithms to solve MOLPs like simplex and Benson's, but I'm seeing differences between how the inputs to those algorithms are expressed and how my problem is framed. What I'm looking for is how to transform or reframe my problem so that it can be solved by these algorithms, or alternatively, how an algorithm can be changed to accommodate the extra constraints.

The main differences I see are:

1. In most MOLPs of the form Ax = b, A is known and x is the thing to be solved for. In my problem, it's the opposite. x is fixed, and A is what needs to be solved for.

2. In my problem, x can contain both positive and negative values, and the objective is to get each row of b as close to zero as possible. I feel like this can be dealt with with slack variables, though, so that's not as much of an issue.

3. How to incorporate my constraints of A's columns adding up to 1, and A's sparcity.

Answer 1

Let $a_{ij}$ represent member of matrix $A$. This can either be the constant $0$ if you want $a_{ij}$ to be $0$ in the solution matrix, or a variable for a linear programming problem. Then you want to add linear constraints:

\begin{alignat}{2} &\!\min_{a} &\qquad& \sum_{i} s_i\\ &\text{subject to} & & \forall j \left(\sum_{i}a_{ij} \leq 1 + \epsilon \right),\\ & & & \forall j \left(\sum_{i}a_{ij} \geq 1 - \epsilon \right),\\ & & & \forall_i \left(\sum_{j}a_{ij}x_j \leq s_i\right),\\ & & & \forall_i \left(\sum_{j}a_{ij}x_j \geq -s_i\right). \end{alignat}

This finds the optimal matrix $A$, with the desired elements set to $0$, that has columns adding up to $1$ (within a certain precision) and minimizes $\left\lVert Ax\right\rVert_1$.