I need to solve the following LP

$$\begin{array}{ll} \text{minimize} & c^T x\\ \text{subject to} & A x = b\end{array}$$


$$A = \begin{bmatrix} 1 & 3 &1&0&0 \\ -2&-2&0&1&0 \\ 2&4&0&0&1 \end{bmatrix}, \qquad b = \begin{bmatrix} 2 \\2\\ 4\end{bmatrix}, \qquad c = \begin{bmatrix} -1\\ -1\end{bmatrix}$$

Matrix $A$ is not full rank. Then the only way to solve that problem is to create an equivalent problem with a full rank matrix? Here for instance:

$$ \min \{ (c,-c) (x^+,x^-)^T : \begin{bmatrix} A & -A \\ -I& 0 \\ 0& -I \end{bmatrix} (x^+,x^-)^T \leq (b, 0,0)^T \} $$

but I don't know how to solve a problem with $x^+$ and $x^-$. Would you have an example ?

So my question is how to solve such a problem, and if you'd recommand my method, how do you use it, especially concerning the $x^+$ part.

  • $\begingroup$ Please clarify what you mean by "full rank". $\endgroup$ – Rodrigo de Azevedo Jun 27 '19 at 7:41
  • $\begingroup$ Does the LP require $\boldsymbol x\ge \boldsymbol 0$? Also, the standard form only assumes the rank of $A$ equals to the number of its rows, which is exactly your case. $\endgroup$ – xskxzr Jun 29 '19 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.