0
$\begingroup$

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?

$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ Yes, but in my case, there is an additional coefficient in the objective function only for the negative part of the free variable. That is, let's say in your example, the objective function is $3(x_1^+ - x_1^- ) + 5(-x_1^-)$ In that case, can we still guarantee one of them will be zero? @calculus $\endgroup$ Commented May 10, 2015 at 4:57
  • $\begingroup$ Yes. In the example above it is obvious, but also, if you would have a min problem. You can summarize it: $3x_1^+-8x_1^-$ $\endgroup$ Commented May 10, 2015 at 5:23
  • $\begingroup$ while the difference here is 2. Nothing guarantees that its parts take different values, (3,1); (4,2) are also valid combinations. $\endgroup$ Commented Nov 2, 2017 at 4:44

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.