Linear Programming Advanced Tricks and Techniques

We introduced Linear Programming in an earlier post but its popularity is still surprising. How can such an apparently restrictive technique find applications in so many fields? Clever users have developed many tricks to push the technique beyond its obvious scope. Some of these tricks are worth understanding.

Helper Variables and Epigraphs

Most algebraic modeling languages for linear programming support basic functions like \(|x|\) and other piecewise linear functions. These are often implemented via their epigraphs. Don’t let the fancy word scare you, the idea is simple enough: first you introduce a new decision variable \(y\) and two constraints (\(y \geq x\) and \(y \geq -x\)). The constraints mean that \(y\) lies anywhere in the blue region in the chart below.

-10 -8 -6 -4 -2 0 2 4 6 8 10 x 0 1 2 3 4 5 6 7 8 9 10 y Epigraph: y ≥ |x| y ≥ |x|

The trick is to make sure that \(y\) enters the objective with a positive coefficient so that the minimization collapses to the smallest feasible value. If we minimize \(y\) subject to \(y \ge x\) and \(y \ge -x\), the best we can do is exactly \(|x|\). The language of mathematics calls that set of points “above” the graph the epigraph: \(\operatorname{epi}(f) = \{(x, y) : y \ge f(x)\}.\) The useful part, of course, is that this gives a way to represent a whole family of nasty-looking functions as a linear program. Want to minimize an absolute value? Introduce a helper variable and bound it above by the relevant piecewise-linear expression. Want a maximum, a hinge loss, or a piecewise cost? The same pattern often works. This is why a modeling language can support things like \(|x|\), \(\max_i x_i\), and other convex piecewise-linear objects without ever letting the solver see anything more exotic than a few extra variables and constraints.

That same general instinct shows up in performance work too. The discovery from the shared note was that a simple-looking expression like \(x - \sum_i x_i\) can trigger terrible scaling because it keeps reusing and recomputing the same shared term over and over. The fix is conceptually the same as the epigraph trick: introduce a temporary variable, cache the common subexpression, and rewrite it so the model exposes the real structure instead of forcing the solver to rediscover it. In cvxpy/cvxpy#3479, the reported slowdown was very dramatic—something like a quadratic-to-cubic-looking blowup in runtime—while a rewrite that cached the shared sum brought the scaling back to near-linear. The lesson is simple: if you can make the hidden structure explicit, you often get both a cleaner model and, more importantly, a much faster one.