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.

  • $\begingroup$ I don't understand the problem statement. What does it mean to minimize each row of $b$? That doesn't sound well-defined. Also, the optimal solution for a multi-objective problem is not well-defined. $\endgroup$
    – D.W.
    Commented Jun 25, 2020 at 5:21

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.