# Linear Optimization Conversion (nested free variable)

1. Sep 12, 2016

### Passanger

1. The problem statement, all variables and given/known data
(This is a mock-up)
Given
maximize(x,y) Ax + | x - y |

s.t.
x + By - C >= 0
y >= 0

A, B, and C are some coefficients.

2. Relevant equations
Linearizing absolute expressions:
z = | x |; where z >= x, z >= -x

Linearizing free variables:
let x = x+ - x-; where x+, x- >= 0 ---- (1)

3. The attempt at a solution
-------------------------------------------------------------------------------------------------------
(I think?) x is not constrained like y (as in y >= 0),
Let x = x+ - x-; where x+, x- >= 0

To linearize the expression | x - y |
Let z = | x - y |; such that z >= ( x - y ) and z >= -( x - y )

So... From (1):
Let z = | x+ - x- - y |; such that z >= ( x+ - x- - y ) and z >= -( x+ - x- - y )
-------------------------------------------------------------------------------------------------------
Therefore, the LP for this problem is
maximize(x,y) A(x+ - x-) + z

s.t.
x+ - x- + By - C >= 0
y >= 0
z >= ( x+ - x- - y )
z >= -( x+ - x- - y )
x+, x- >= 0

... ?

2. Sep 17, 2016