How to reformulate this model in standard form?

Question

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

Answer 1

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.