How to reformulate the following linear programming model into an equivalent model that is a linear program in standard form?:

Maximize $-e^T |x|$
subject to $Ax \geq b$
x unrestricted

where e = (1, 1,...,1)
and |x| = abs(x)

Standard form in this case would be:

$min_x$ $c^Tx$
Ax = b
x $\geq$ 0

  • $\begingroup$ Suppose you have $4$ (decision) variables is then your objective function $-|x_1|-|x_2|-|x_3|-|x_4|$? $\endgroup$ – callculus Oct 10 '19 at 5:18
  • $\begingroup$ I guess so, I also find it an odd formulation. It is mainly about the formulation. I have a hunch that the absolute value in the objective can be exchanged with the $\geq$ in the standard form. $\endgroup$ – Julius Baer Oct 10 '19 at 6:23

You can tranform the variables $|x_j|=x_j^++x_j^-$ and $x_j=x_j^+-x_j^-$ , with $x_j^+,x_j^-\geq 0$

For 2 decision variables and 2 constraints we get

$\texttt{max} \ \ -x_1^+-x_1^--x_2^+-x_2^- $

$a_{11}\cdot \left( x_1^+-x_1^-\right)+a_{12}\cdot \left( x_2^+-x_2^-\right)\geq b_1$

$a_{21}\cdot \left( x_1^+-x_1^-\right)+a_{22}\cdot \left( x_2^+-x_2^-\right)\geq b_2$

$x_1^+,x_1^-,x_2^+,x_2^-\geq 0$

  • Maximizing $f(\textbf x)$ is equivalent to minimizing $-f(\textbf x)$
  • And we have to subtract surplus variables ($s_i$) for each $\geq$-constraint to get equations.

$\texttt{min} \ \ x_1^++x_1^-+x_2^++x_2^- $

$a_{11}\cdot \left( x_1^+-x_1^-\right)+a_{12}\cdot \left( x_2^+-x_2^-\right)-s_1=b_1$

$a_{21}\cdot \left( x_1^+-x_1^-\right)+a_{22}\cdot \left( x_2^+-x_2^-\right)-s_2= b_2$

$x_1^+,x_1^-,x_2^+,x_2^-,s_1,s_2\geq 0$

This is what you wanted.

  • 1
    $\begingroup$ You also need $s_i \ge 0$. $\endgroup$ – Rob Pratt Oct 10 '19 at 12:52
  • 1
    $\begingroup$ And subtract $s_i$ instead of adding. $\endgroup$ – Rob Pratt Oct 10 '19 at 13:00
  • $\begingroup$ @RobPratt 100% right. No idea why I´ve witten it this way. $\endgroup$ – callculus Oct 10 '19 at 16:07
  • $\begingroup$ Looks good now. $\endgroup$ – Rob Pratt Oct 10 '19 at 16:59
  • $\begingroup$ what would be a numbered example? $\endgroup$ – Julius Baer Oct 14 '19 at 8:12

Your Answer

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

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