# How to reformulate this model in standard form?

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

• Suppose you have $4$ (decision) variables is then your objective function $-|x_1|-|x_2|-|x_3|-|x_4|$? – callculus Oct 10 '19 at 5:18
• 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. – 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.

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