Transforming the Variables

Slack and surplus variables change the form of a constraint. A different family of substitutions changes the variables themselves: splitting a sign-unrestricted variable into a difference of two nonnegatives, shifting a variable with a nonzero lower bound, and negating a nonpositive one. Each preserves the feasible set and each carries its own error, the most consequential being that the split is not unique.

Definition

Standard form requires every variable to be nonnegative. Three substitutions achieve that, each replacing a variable rather than adding to a constraint.

Sign-unrestricted variables. If $x_{j}$ carries no sign restriction, substitute

x_{j} = x_{j}^{+} - x_{j}^{-}, x_{j}^{+} \geq 0, x_{j}^{-} \geq 0,

everywhere $x_{j}$ appears, in the objective and in every constraint.

Nonzero lower bounds. If $x_{j} \geq ℓ$ with $ℓ \neq 0$ , substitute $x_{j} = u_{j} + ℓ$ with $u_{j} \geq 0$ . The constraint $x_{j} \geq ℓ$ then disappears, having been absorbed into the definition of $u_{j}$ , and a constant $c_{j} ℓ$ appears in the objective which must be carried separately.

Nonpositive variables. If $x_{j} \leq 0$ , substitute $x_{j} = - v_{j}$ with $v_{j} \geq 0$ . Every coefficient of $x_{j}$ changes sign.

Upper bounds are not variable transformations. A restriction $x_{j} \leq u$ is an ordinary constraint and takes a slack variable like any other. It is sometimes handled specially inside an algorithm for efficiency, but that is an implementation choice, not part of the conversion.

The split is not unique. For any $t \geq 0$ , the pair $(x_{j}^{+} + t, x_{j}^{-} + t)$ represents the same $x_{j}$ . Every value of $x_{j}$ therefore corresponds to infinitely many feasible pairs, so a converted program with a split variable has infinitely many optimal solutions whenever the original has one, all describing a single original solution.

Formal statement

Sign-unrestricted: $x_{j} = x_{j}^{+} - x_{j}^{-}$ , $x_{j}^{\pm} \geq 0$ ; non-unique, since $(x_{j}^{+} + t, x_{j}^{-} + t)$ gives the same $x_{j}$ for any $t \geq 0$ . Lower bound $x_{j} \geq ℓ$ : $x_{j} = u_{j} + ℓ$ , $u_{j} \geq 0$ , contributing $c_{j} ℓ$ to the objective. Nonpositive $x_{j} \leq 0$ : $x_{j} = - v_{j}$ , $v_{j} \geq 0$ .

Assumptions and scope

A substitution must be applied everywhere the variable occurs. Replacing it in the constraints but not the objective, or in one constraint but not another, produces a program describing a different problem rather than an equivalent one.
The split of a sign-unrestricted variable is not unique, so the converted program has infinitely many optimal solutions whenever the original has one. Reporting them as distinct plans is a misreading of the conversion, not a discovery about the problem.
Shifting a lower bound leaves a constant in the objective. Dropping it gives the right optimal solution and the wrong optimal value.
The substituted variables are decision variables of the converted program and carry nonnegativity like any other. The pair from a split is not constrained to have one member zero; nothing enforces that and nothing needs to.
An upper bound is a constraint, not a variable transformation. It takes a slack variable, and treating it as a substitution removes a restriction the problem actually imposes.

Worked material

Example

One variable of each kind

Unrestricted. $x$ free, appearing as $3 x$ in the objective and $x \leq 7$ in a constraint. Substitute $x = x^{+} - x^{-}$ :

Objective term becomes $3 x^{+} - 3 x^{-}$ ; the constraint becomes $x^{+} - x^{-} \leq 7$ , which then takes a slack variable like any inequality. Two new variables, both nonnegative.

Nonpositive. $y \leq 0$ , appearing as $- 4 y$ in the objective and $2 y \geq - 10$ in a constraint. Substitute $y = - v$ with $v \geq 0$ :

Objective term becomes $- 4 (- v) = 4 v$ ; the constraint becomes $- 2 v \geq - 10$ , equivalently $v \leq 5$ . One new variable, and every sign involving it has flipped.

Lower-bounded. $z \geq 3$ , appearing as $6 z$ in the objective and $z + w \leq 20$ in a constraint. Substitute $z = u + 3$ with $u \geq 0$ :

Objective term becomes $6 (u + 3) = 6 u + 18$ , so $6 u$ enters the program and the constant $18$ is set aside. The constraint becomes $u + 3 + w \leq 20$ , that is $u + w \leq 17$ . The restriction $z \geq 3$ is discarded, having been absorbed.

Reading back. $x = x^{+} - x^{-}$ , $y = - v$ , $z = u + 3$ , and the reported optimal value must have $18$ added to it before it is comparable with the original objective.

Non-example

Substitutions that do not do what they appear to

Not a variable transformation: an upper bound. $x \leq 12$ is a constraint. It takes a slack variable and becomes $x + s = 12$ . Substituting $x = 12 - w$ to 'make it nonnegative' also removes the restriction that $x \geq 0$ , which was a genuine part of the problem, and produces a different feasible set.

Not sufficient: substituting in the constraints only. Replacing $q$ by $q^{+} - q^{-}$ in every constraint while leaving $3 q$ in the objective produces a program whose objective refers to a variable that no longer exists. Where a solver tolerates it, the objective is silently wrong.

Not equivalent: dropping the shift constant. Converting $z \geq 3$ by $z = u + 3$ and forgetting the $18$ in the objective gives the correct optimal $u$ , hence the correct $z$ , and an optimal value short by $18$ . The solution is right and the number reported for it is wrong. A failure mode that survives every check on the point itself.

Not a valid simplification: forcing one of a split pair to zero. Writing 'take $q^{-} = 0$ since only one is needed' converts a sign-unrestricted variable into a nonnegative one. That is a different problem, and it will be infeasible whenever the original optimum requires $q < 0$ .

Not two solutions: two split pairs giving one value. The pairs $(5, 0)$ and $(9, 4)$ both represent $q = 5$ . A solver reporting them at two iterations has not found two plans.

Contrast

Non-uniqueness of the sign-unrestricted split

The substitution $x = x^{+} - x^{-}$ looks like a definition, and it is natural to read it as assigning each $x$ a specific pair. It does not.

The arithmetic. For any $t \geq 0$ ,

(x^{+} + t) - (x^{-} + t) = x^{+} - x^{-} = x .

Adding the same amount to both members leaves the difference unchanged and both members nonnegative. So $x = 5$ is represented by $(5, 0)$ , by $(9, 4)$ , by $(1000, 995)$ , and by infinitely many other pairs, all feasible.

What that does to the converted program. Suppose the original has a unique optimal solution with $x = 5$ . The converted program has infinitely many optimal solutions, the entire ray ${(5 + t, t) : t \geq 0}$ in those two coordinates, every one with the same objective value, because the objective contains $c (x^{+} - x^{-})$ and the $t$ cancels there too.

How this is misread. A solver is run twice, or a log is examined across iterations, and different values of $x^{+}$ and $x^{-}$ appear. The natural conclusion is that the problem has several optimal plans. It does not: it has one, reported in a representation that admits many spellings. Reporting $(5, 0)$ and $(9, 4)$ as two answers means reporting $x = 5$ twice.

What is genuinely multiple. Multiple optima in the original problem means several distinct values of $x$ attaining the optimum, which comes from the objective being parallel to a binding constraint. The test is to read the pairs back: if $x^{+} - x^{-}$ differs between two reported solutions, the optima are genuinely distinct; if it is the same, they are one solution written differently.

The habit. Always report the recovered original variables, never the converted ones. The recovery rule is part of the conversion, not an afterthought, which is why it belongs in the written record alongside the transformed program.

Common errors

Common misconception

When a sign-unrestricted variable is split into a difference of two nonnegative variables, the resulting pair is determined, so each optimal solution of the converted program is a distinct solution of the original.

Related units

Requires

Converting a Linear Program to Standard Form

Connected

Basic Solutions (used by)

Learn this topic

Transforming the Variables

Used in

Linear Programming

Sources

Introduction to Linear Optimization (1997)

Transforming the Variables

Assumptions and scope

Worked material

One variable of each kind

Substitutions that do not do what they appear to

Non-uniqueness of the sign-unrestricted split

Common errors

Related units

Requires

Connected

Learn this topic

Used in

Sources

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history