I have a free variable in my formulation. In the objective function, this free variable has a cost, and another cost coefficient which is only incurred when the free variable is negative. I used the technique where we write the free variable as the difference of two non-negative variables, and used only one of those variables when writing the cost coefficient which is incurred when the free variable is negative. However, at the optimal solution, both of those variables are positive.
Does that mean, in general, when we use the "write it as the difference of two nonnegative variables" technique, we cannot separate these two (newly defined) variables from each other? That is, do they have to incur the same coefficients (one positive, the other negative of course) in the objective function and we can't treat them as separate variables when writing the constraints?
Best Answer
They are different variables. But at the optimal solution, if it exists, one of it will be zero.
Suppose the free variable is $x_1$. Then you define $x_1=x_1^+-x_1^-$ and $x_1=x_1^+,x_1^-\geq 0$
small problem:
$\texttt{max} \ \ 3x_1$
$6x_1\leq 12$
$x_1 \ \ \texttt{free}$
transformed small problem
$\texttt{max} \ \ 3(x_1^+-x_1^-)$
$6(x_1^+-x_1^-)\leq 12$
$x_1^+,x_1^-\geq 0$
To maximize the objective function, $x_1^+$ has to as big as possible. And $x_1^-$ has to be as small as possible. Thus $x_1^+=2$ and $x_1^-=0 \Rightarrow x_1=2$