If I want to convert the following linear problem into a standard form: $$\min z=4x_1+2x_2+x_3$$ Subject to $$-x_1+3x_2-x_3\ge1$$ $$5x_1+3x_3=5$$ $$x_1+x_2+x_3\le1$$ $$-1\le x_1, x_2\le2,x_3\ge0$$ I understand how to turn $\min z$ into $\max z$ and how to use the slack variables. What I don't get is how to do the change of variables for the constraints. In the answer I am suppose to introduce the variable $x_1'=x_1-1$, $x_2'=-x_2-2$. Why do we write it like this? What is the logic behind it? And what if the constraint is with the absolute value like: $|x_1|\le1$?

  • $\begingroup$ Presumably your standard form requires all variables to have $x_{I} >= 0$. The substitutions you’ve listed accomplish that. $\endgroup$ – Brian Borchers Feb 24 '18 at 4:43

As suggested by the first comment, in the standard form, you have nonnegative decision variables. $\require{extpfeil} \Newextarrow{\xiff}{5,5}{0x21d4}$

\begin{alignat}{3} -1 &\le x_1 &\iff x_1 + 1 &\ge 0 &\quad \xiff[]{\large \text{set } x_1'=x_1+1} \quad x_1' &\ge 0 \\ x_2 &\le 2 &\iff -x_2 + 2 &\ge 0 &\quad \xiff[]{\large \text{set } x_2'=-x_2+2} \quad x_2' &\ge 0 \end{alignat}

If you have $|x_1| \le 1$, you have to split it into two inequalities and include them in the constraints in the canonical form.

$$|x_1| \le 1 \iff \begin{cases} x_1 &\le 1 \\ -x_1 &\le 1 \end{cases} $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.