Transforming the Variables

A variable bounded below by 4, or free to go negative, cannot enter a method that assumes every variable starts at zero. Each awkward case has a substitution that fixes it, and each substitution has to be carried everywhere the variable appears, including into the answer you eventually report back.

The conversion unit introduced the splitting substitution as one step among four. This unit is about the substitutions themselves: which one each restriction calls for, what each leaves behind in the objective, and how to read a converted solution back to the problem you started with.

The reason it warrants separate treatment is the non-uniqueness. A split variable can be represented in infinitely many ways, and the consequence, that a converted program has infinitely many optimal solutions where the original had one, surprises people and is regularly misreported as a discovery about the problem.

This unit assumes you can convert a program to standard form and know why standard form demands nonnegative variables.

Two different operations are both called part of conversion, and running them together is the first thing to avoid.

Slack and surplus variables change the shape of a constraint. An inequality becomes an equality by absorbing the difference between the two sides. The original variables are untouched; something new sits alongside them.

These substitutions change the variables themselves. The original variable vanishes from the program and something else stands in its place everywhere it occurred. Nothing is added to any constraint. A symbol is replaced.

The splitting substitution deserves the most attention. Any real number is a difference of two nonnegative numbers: $5=5-0$, and $-3=0-3$. That is the substitution. But $5$ is also $9-4$, and $100-95$, and nothing in the program prefers the tidy version. The representation is genuinely not unique.

So convert a program with one optimal solution and a split variable, and the converted program has a whole ray of optimal solutions. Every one of them encoding the same original answer. Reporting them as distinct plans means reporting one plan repeatedly.

The shifting substitution works differently, as a change of origin rather than an addition. Measure a variable from its lower bound instead of from zero, and the bound becomes automatic: the constraint stating it can be discarded because the new variable cannot violate it. What survives is a constant in the objective, and that constant is the thing most often dropped.

The canonical statement gives the three substitutions. In practice the difference is what each one costs and what has to be undone afterwards.

A free variable doubles into two columns, and the split is not unique. $x_j=x_j^{+}-x_j^{-}$ admits infinitely many representations of the same value: $3=5-2=100-97$. Every one is feasible and every one gives the same objective, so a solver may return any of them. Reading $x_j$ back means taking the difference, never either component alone.

A nonzero lower bound leaves a constant behind. Substituting $x_j=u_j+\ell$ removes the constraint entirely, which is the point, but it puts $c_j\ell$ into the objective. That constant does not affect which point is optimal and does affect the reported value, so it must be carried and added back. Dropping it is the commonest error in the conversion, and it is invisible: the solution is right and the number beside it is wrong.

Every substitution has to be reversed in the report. The solver answers in $u_j$, $v_j$, $x_j^{+}$ and $x_j^{-}$, which are artefacts of the form rather than quantities anybody asked about. The model was written in the original variables and the answer has to arrive in them.

Classify every variable by its restriction. Go through the variable list and record, for each, whether it is already nonnegative, unrestricted in sign, nonpositive, or bounded below by a nonzero constant. Do this before substituting anything, because the choice of substitution follows from the classification.

Leave the already-nonnegative variables alone. A variable with $x_j\ge 0$ needs nothing. Substituting anyway adds variables and columns for no reason.

Substitute each restricted variable according to its class. Unrestricted: $x_j=x_j^{+}-x_j^{-}$. Nonpositive: $x_j=-v_j$. Lower-bounded: $x_j=u_j+\ell$.

Carry each substitution through the objective and every constraint. Work systematically along the program rather than by eye. A variable appearing in four constraints must be replaced in all four, and its appearance in the objective is the one most often overlooked.

Collect the constants a shift produces. Substituting $x_j=u_j+\ell$ into a constraint changes its right-hand side; substituting into the objective leaves an additive constant. Move the constraint constants into the right-hand sides and hold the objective constant aside. It does not affect which point is optimal, and it does affect the reported value.

Discard the restrictions the substitutions absorbed. The row $x_j\ge \ell$ is gone, as is the declaration that $x_j$ is unrestricted. What remains is the nonnegativity of the new variables.

Confirm every variable is nonnegative. Original untouched variables, slack and surplus variables, split pairs, shifted variables, negated variables. Every one must carry a nonnegativity restriction, or the program is not in standard form.

Write down how to read the answer back. Record $x_j=x_j^{+}-x_j^{-}$, or $x_j=u_j+\ell$, or $x_j=-v_j$, together with the objective constant. Without this the converted solution cannot be reported in the original problem's terms.

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

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

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

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

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

Objective term becomes $6(u+3)=6u+18$, so $6u$ enters the program and the constant $18$ is set aside. The constraint becomes $u+3+w\le 20$, that is $u+w\le 17$. The restriction $z\ge 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.

Problem. Convert to standard form:

Goal. A standard-form program, plus the rule for reading its answer back.

Relevant principle. Classify first, substitute everywhere, and hold the objective constant aside.

Step 1: classify. $p$ is bounded below by $2$; $q$ is unrestricted; $r$ is nonpositive.

Step 2: choose the substitutions. $p=u+2$ with $u\ge 0$. $q=q^{+}-q^{-}$ with $q^{\pm }\ge 0$. $r=-v$ with $v\ge 0$.

Step 3: the objective.

Maximising this is maximising $4u+3q^{+}-3q^{-}+2v$, with the constant $8$ held aside. Negating for a minimisation:

Step 4: the first constraint. $(u+2)+(q^{+}-q^{-})+(-v)\le 30$, so $u+q^{+}-q^{-}-v\le 28$. Adding a slack: $u+q^{+}-q^{-}-v+s_1=28$, $s_1\ge 0$.

Step 5: the second constraint. $2(u+2)-(q^{+}-q^{-})\ge 5$, so $2u+4-q^{+}+q^{-}\ge 5$, that is $2u-q^{+}+q^{-}\ge 1$. Subtracting a surplus: $2u-q^{+}+q^{-}-e_1=1$, $e_1\ge 0$.

Step 6: discard the absorbed restrictions. $p\ge 2$ is gone, absorbed into $u\ge 0$. The declarations that $q$ is free and $r$ nonpositive are gone, replaced by nonnegativity on their substitutes.

Result.

subject to

Check. Minimisation, two equalities, six variables all nonnegative. Standard form holds.

Reading back. If the minimum is $w$, the original maximum is $-w+8$. The original variables are $p=u+2$, $q=q^{+}-q^{-}$, and $r=-v$.

What is easiest to lose here. The constant $8$, and the $+4$ that the shift pushed into the second constraint's right-hand side. Both come from the same substitution, and dropping either gives an answer that is internally consistent and wrong.

Not a variable transformation: an upper bound. $x\le 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\ge 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 $3q$ 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\ge 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 .

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.

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\ge 0$,

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\ge 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.

1. Convert $max2a+5b$ subject to $a+b\le 9$, $a\ge 4$, $b$ free, to standard form. Give the recovery rule and the objective constant.

2. A variable $x$ satisfies $x\le 0$ and appears as $-3x$ in the objective and $x+y\ge -6$ in a constraint. Substitute and give both rewritten expressions.

3. Show that $(7,2)$ and $(12,7)$ represent the same value of a split variable, and state what that value is.

4. A colleague converts $z\ge 5$ by substituting $z=u+5$ and reports an optimal value of $40$. What must be done to that number before it is comparable with the original objective, and why does the optimal point need no correction?

5. Explain why $x\le 12$ is not handled by a variable substitution, and give the correct treatment.

Three substitutions make variables nonnegative, and each replaces a variable rather than adding to a constraint. Unrestricted: $x=x^{+}-x^{-}$. Nonpositive: $x=-v$. Bounded below by $\ell$: $x=u+\ell$.

An upper bound belongs to the other family: it is a constraint and takes a slack variable.

Every substitution must be carried through the objective and every constraint. The objective is where an omission is easiest and least visible.

A shift leaves a constant in the objective and changes the right-hand sides of the constraints the variable appears in. The constant does not affect which point is optimal and does affect the value reported for it.

The split of a sign-unrestricted variable is not unique: adding the same amount to both members represents the same original value. So a converted program has infinitely many optimal solutions wherever a split variable appears, and they are one original solution written many ways rather than several plans.

Record the recovery rule when you record the converted program. A solution expressed in substituted variables is not an answer to the question that was asked.