How to convert linear program into standard form?

Suppose I wish to solve the linear program $$\begin \text & c^T x\\ \text & Ax \leq b\\ & x > 2016\end$$ 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$ .

• optimization
• linear-programming

$\begingroup$ You cannot use a strict inequality, as you won't have any minimizer (for any solution you claim, you can always create a slightly better). Hence, you have to settle for a strict inequality $x \geq 2016 + \epsilon$ where $\epsilon$ is a small number which you pick (based on what is strict enough for your application) $\endgroup$

1 Answer 1

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$

$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$

The decision variables are all non-negative.