0
$\begingroup$

In two books of Dantzig, there is a theorem which attribute to Tucker, but no citation is provide. Generally, every one unrestricted variable can be transformed two non-negative variables. It says that n unrestricted variable can be transformed n+1 non-negative variables, instead 2n variables.

enter image description here

enter image description here

enter image description here

How this result can be proved, or where can find the proof?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The idea of the first transformation with $2n$ variables is to interpret $x_j'$ as the positive part $\max(x_j,0)$ and $x_j''$ as the negative part $\max(-x_j,0)$.

For the second transformation with $n+1$ variables, $x_0$ represents the most negative part $$\max_{j\in\{1,\dots,n\}} \max(-x_j,0),$$ and $x_j'$ represents $x_j+x_0$.

$\endgroup$
2
  • $\begingroup$ Many thanks! I have another related question about absolute value. If the objective is min c|x|, where c>0, then it is possible to linearlize by using |x|=x1+x2 and x=x1-x2. But is it possible linearlize the MP if c<0, or with constraint like 2|x|+3|y|=4? Btw, I find someone use y>x and y>-x to linearlize a MP with absolute value. Is the approach equivalent to, or more powerful than |x|=x1+x2 and x=x1-x2. $\endgroup$
    – zjdxsmjd
    Commented Mar 1, 2023 at 14:53
  • $\begingroup$ Glad to help. Please start a new post for each additional question. $\endgroup$
    – RobPratt
    Commented Mar 1, 2023 at 17:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .