Skip to content
Tutorials Center
My learning

Topics

Lesson 9 of 38 Ā· Modelling

Modelling Tricks: Absolute Values, Min-Max and Goals

Make non-obvious problems linear: absolute values, minimize the maximum, maximize the minimum, goal programming and piecewise costs, with runnable Python.

Linear programming only allows linear functions, but many natural goals look nonlinear: "minimize the total deviation", "make the worst-off team as happy as possible", "come as close as you can to this target". With a few reformulation tricks, a large class of such problems turns into ordinary LPs. This lesson collects the tricks you will use again and again.

Trick 1: absolute values in the objective

Suppose you want to minimize |x| (or sum |e_i|). The function |x| is convex but not linear. Introduce a helper variable t with

TEXT
minimize t     subject to   t >= x    and    t >= -x

Since t is at least both x and -x, it is at least |x|; and since we minimize t, it will come down to exactly |x|. This works when the absolute value penalizes (appears with a positive weight in a minimization). The same idea in a maximization of -|x| is also fine, but maximizing |x| is not possible this way: that is a non-convex problem.

An alternative: split x = x⁺ - x⁻ with x⁺, x⁻ >= 0 and minimize x⁺ + x⁻.

Example: least absolute deviations regression

Fit a line y = a + bĀ·x by minimizing sum |y_i - a - b x_i|. Compared with least squares, this is far less sensitive to outliers. Each residual gets a helper e_i >= |y_i - a - b x_i|, written as two linear inequalities.

Python L1 regression is an LP

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The LAD line stays close to the true trend of about slope 2, while the least-squares line is dragged up by the outlier.

Trick 2: minimize the maximum (minimax)

Want to balance a workload so that the busiest worker has as little as possible? Minimize max_i f_i(x). Introduce t and require t >= f_i(x) for every i:

TEXT
minimize t     subject to    f_i(x) <= t   for all i

This is the minimax or bottleneck pattern. Examples: minimize the maximum load on any machine, the longest delivery time, the worst-case error (Chebyshev approximation).

Trick 3: maximize the minimum (maximin)

Symmetrically, to make the worst-off as well off as possible: maximize t subject to f_i(x) >= t for every i. Use it for fairness (maximize the smallest share) or reliability (maximize the weakest link).

Python Balance a workload with minimax

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All three loads come out equal: the LP levels them exactly, because the optimum lowers the maximum until a bottleneck cannot go any lower.

Trick 4: goal programming

Real goals conflict: "profit at least 5000", "overtime at most 20 hours", "emissions at most 100". If all cannot be met, minimize the deviation from each goal. For a goal g(x) = target, introduce non-negative deviation variables d⁺ (over) and d⁻ (under):

TEXT
g(x) + d⁻ - d⁺ = target,     d⁺, d⁻ >= 0

Then minimize a weighted sum of the unwanted deviations. For a "profit at least 5000" goal only d⁻ (shortfall) is unwanted; for "overtime at most 20" only d⁺ (excess) is. Weights express priorities.

Python Goal programming

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Change the weights and you change which goal gives way: that is the real content of goal programming.

Trick 5: piecewise-linear costs

A convex piecewise-linear cost (for example, quantity discounts that make marginal cost increase, or overtime rates) can be modelled with one variable per segment. If the first 100 units cost 5 each, the next 50 cost 7 and the next unit costs 10, let y1 <= 100, y2 <= 50, y3 >= 0 and x = y1 + y2 + y3, with cost 5 y1 + 7 y2 + 10 y3. The solver fills cheaper segments first because that minimizes cost, so no ordering constraints are needed. For concave costs (volume discounts where marginal cost falls) the trick fails and you need integer variables later in the course.

These tricks need the right direction of convexity. Minimizing a convex function (|x|, max, convex piecewise cost) works; minimizing a concave one, or maximizing a convex one, does not and requires integer programming.

Trick 6: linear-fractional objectives (ratios)

To maximize a ratio such as profit / hours over a linear region, the Charnes-Cooper transformation turns it into an LP by scaling variables. It is beyond the first pass of this course, but know that a ratio objective is not automatically hopeless.

Check your understanding

Quick check Ā· 4 questions

of 4 answered You scored / 4 Ā· perfect!

  1. 1. How do you minimize |x| with a helper variable t?

    t is forced above both x and -x, hence above |x|, and minimization pushes it down to |x|.
  2. 2. To balance a workload so the busiest machine is as lightly loaded as possible you

    Minimizing an upper bound on every load is exactly minimizing the maximum.
  3. 3. In goal programming, which deviation do you penalize for the goal 'overtime at most 20 hours'?

    Only exceeding the 20-hour target is unwanted, so penalize the positive deviation.
  4. 4. Why can't you maximize |x| with the t >= x, t >= -x trick?

    With maximization the constraints t >= x and t >= -x do not stop t from growing, so t is no longer tied to |x|.

Summary

  • Absolute values and L1 error: use t >= x, t >= -x, or split into positive and negative parts.
  • Minimax: minimize t with f_i(x) <= t; maximin: maximize t with f_i(x) >= t.
  • Goal programming: deviation variables d⁺, d⁻, penalize the unwanted side.
  • Convex piecewise-linear costs need one variable per segment, no ordering constraints.
  • These tricks work for convex objectives; concave/non-convex ones need integer programming.

Next: The Geometry of Linear Programs