Four requirements that look non-linear are linear after an auxiliary variable is introduced, and all four are the same argument: the rewrite is legal exactly when the direction of optimisation forces the auxiliary variable to the value you intended. Flip the direction and three of the four stop being about the original problem at all — which is something a reader can detect, by solving both and subtracting.
Core ideas
There is one idea here and it is repeated four times. The four cases are practice at the same argument, not four things to memorise.
Adding t with the rows t ≥ piece₁ and t ≥ piece₂ does not make t the larger piece; it makes t at least the larger piece. Minimising t squeezes it down onto that piece, and only then is the rewrite an equality in disguise.
Maximise t in that model and nothing above it stops it climbing: the programme is unbounded while the original still has a finite answer at a corner. The rows did not change — the claim about where the optimiser pushes t did.
The lab optimises the original by enumerating the corners of each part of the region where one piece is the one that counts, and the rewrite by the simplex engine. Subtracting the two answers is a test that can fail, which is why it is worth running.
The material
A free variable, an absolute value, a smallest largest piece, and a cost quoted in two bands — with the condition stated each time.
The rewrites below sit on one region: x + y ≤ 8, x ≤ 5, y ≤ 6 and 2x + 3y ≥ 12. For the first three, x is free to go negative as far as −4; for the price-band rewrite it is held at or above zero, because a quantity bought under a price schedule cannot be negative. What changes between them is the objective, and what each rewrite does is trade a non-linear objective for extra variables and extra rows.
A variable x with no sign restriction is carried as x = x⁺ − x⁻ with x⁺ ≥ 0 and x⁻ ≥ 0. Every occurrence of x in every row and in the objective is replaced by that difference.
Any pair with the right difference gives the same objective value, so nothing needs to push either part anywhere in particular. This is the one rewrite of the four that is legal whichever way the objective is pushed.
With the objective 3x + 2y minimised, the answer is 3 at x = −3, y = 6, and the rewrite reports x⁺ = 0, x⁻ = 3: the negative value is carried by the second part. Maximised, the answer is 21 at (5, 3) with x⁻ = 0. Both agree with the original exactly, which is what “legal in either direction” means in practice.
The same two parts serve for |x|, as their sum rather than their difference. That sum is |x| only when at least one of x⁺ and x⁻ is zero, because otherwise both could be inflated together without changing x. Minimising a non-negative multiple of x⁺ + x⁻ does push one of them to zero. Maximising does the opposite.
Minimise 2|x| + 5y: the original is 40/3 at (5, 2/3) by corner enumeration, the rewrite is 40/3 by the simplex engine with x⁺ = 5 and x⁻ = 0, and the difference is exactly zero. Now maximise the same expression: the original is 36 at (−3, 6) and the rewrite is unbounded, because x⁺ and x⁻ climb together for ever with nothing to stop them. A reader who only ran the rewrite would have no way to notice.
Let f(x) = max(p₁(x), p₂(x), …) with each pᵢ linear. Then minimising f over a region is the same problem as minimising t over the same region with the rows t ≥ pᵢ(x) added, one per piece, and t free.
The rows make t at least every piece, so t ≥ f(x) at every feasible point, and minimising cannot leave t above f(x). Maximising can and does: the rewritten programme is then unbounded, and it is a different problem rather than a worse answer to this one.
Minimise max(2x + y, −x + 5y) on the region and both routes report 132/17, at x = 48/17, y = 36/17, with t = 132/17 sitting exactly on the two pieces where they cross. The fraction is worth noting: the corner that wins is the crossing of the boundary of the region with the line where one piece overtakes the other, and nothing about it rounds.
Suppose the first 3 units of x cost 2 each and every unit after that costs 5. Split the quantity into one variable per band, cap the first at 3, and price them separately. A minimiser fills the cheaper band first — and the cheaper band is the earlier one only when the later band costs more. That condition is convexity, and it is the condition rather than the background.
Quote the first 3 units at 5 each and everything after at 2. The true cheapest cost on this region is 16, at (0, 4). The band model reports 38/3, with x(1) = 0 and x(2) = 5: it has bought five units out of the second band without filling the first, which the price schedule does not allow. The model is not a worse answer to the question; it is a cheaper answer to a question with no cost schedule behind it.
So the rule to carry away is not “these four tricks work”. It is that an auxiliary variable comes with a sentence — what forces it to the value I intend — and that the sentence is checkable by solving the original some other way and subtracting.
Interactive
An auxiliary variable is legal exactly when the direction forces its value
Method
The first two steps are the argument and the last two are the evidence. Skipping the evidence is how an illegal rewrite ships.
t is supposed to be the largest piece; x⁺ + x⁻ is supposed to be |x|. Writing the intention down is what makes the next step possible.
“Minimising t squeezes it onto the largest piece.” If the sentence needs the objective to be pushed the other way, the rewrite is legal the other way and not this way.
In two variables, enumerate the corners — and on a piecewise objective, the corners of each part on which one piece is the one that counts, because the objective is linear on each of those.
Zero is the only acceptable answer. A rewrite that reports a better objective value than the original has not improved anything; it has escaped the constraints of the question.
One model, two directions. The first is a legal rewrite and the second is a different problem, and the only visible difference is which way the objective is pushed.
The minimised pair agree to the last fraction, and they were computed by different methods on different models. The maximised pair do not agree at all, and the reason is one sentence: minimising t squeezes it onto the largest piece, and maximising t lets it float away from every piece at once.
For a faded rehearsal, take the absolute-value rewrite with the same region and the objective 2|x| + 5y. The supplied first move is the pieces: |x| is the larger of x and −x, so 2|x| + 5y is the larger of 2x + 5y and −2x + 5y. Minimise it both ways — by the corners of the two parts, and by the split model — then flip to maximise and say, before running anything, which of the two will report a finite answer.
You should be able to rewrite an absolute value and a min-max objective as linear programmes, say what forces each auxiliary variable to its intended value, solve the original another way, and read a non-zero difference as the rewrite being a different problem.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.