[Math] How to convert linear program into standard form

linear programmingoptimization

Suppose I wish to solve the linear program

$$\begin{array}{ll} \text{maximize} & c^T x\\ \text{subject to} & Ax \leq b\\ & x > 2016\end{array}$$

where $x>2016$ means that all components of $x$ are strictly larger than $2016$. How do I convert this into standard form while still maintaining my desired constraints?

I realize that one way to change the "$>$" to a "$\geq$" is to change the constraints to $Ax \leq b$, $x-s \geq 2016$, and $x,s\geq 0$, but this does not guarantee that my decision vector $x$ consists of all components that are larger than $2016$.

Best Answer

The standard form is sometimes defined with inequalities ($\leq$) and sometimes with equalities. If you want to begin with an algorithm it is useful to have equalities.

If all variables has to be equal or greater than $2016$ then you have to introduce slack variables like you proposed.

$x_1\geq 2016, x_2\geq 2016, x_3\geq 2016, \ldots, x_n\geq 2016$

becomes

$x_1-s_1= 2016, x_2-s_2= 2016, x_3-s_3= 2016, \ldots, x_n-s_n= 2016$

with $x_1, x_2,\dots, x_n, s_1, s_2, s_3, \ldots s_n \geq 0$

Here you get $n$ additional constraint. To get an initial solution artifitial variables have to be intoduced.

$x_1-s_1+a_1= 2016, x_2-s_2+a_2= 2016, x_3-s_3+a_3= 2016, \ldots, x_n-s_n+a_n= 2016$

with $x_1, x_2,\dots, x_n, s_1, s_2, s_3, \ldots s_n, a_1, a_2,\dots, a_n \geq 0$

The initial solution is $x_1=x_2=x_3=\ldots=x_n=s_1= s_2= s_3= \ldots s_n=0$

$a_1=a_2=a_3=\ldots=a_n=2016$

The decision variables are all non-negative.