Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 38 · Linear and Quadratic Programs

Linear Programs

Learn linear programs in standard form, why the best point sits at a vertex, how LP duality works, and how to solve one with SciPy, including infeasible and unbounded cases.

A linear program (LP) minimizes or maximizes a linear function over a region cut out by linear inequalities. It is the oldest and most widely used convex problem: diets, production plans, shipping routes, and flight schedules are all LPs. LPs are also easy to solve, even with millions of variables.

You met a small LP in the sensitivity lesson. Here we study its structure properly.

The form of an LP

A common form, with variables x ∈ ℝⁿ:

Text
maximize    cᵀx
subject to  A x ≤ b
            x ≥ 0

Every LP can be rewritten into this shape (flip signs to turn a minimization into a maximization, split a free variable into two non-negative parts, and so on). The region {x : Ax ≤ b, x ≥ 0} is a polyhedron: a convex shape with flat faces, straight edges and sharp corners called vertices.

Our running example (the workshop from the previous chapter):

Text
maximize    3x + 2y
subject to  x + y  ≤ 4
            x + 3y ≤ 9
            x      ≤ 3
            x, y   ≥ 0

Why the optimum is at a vertex

The objective cᵀx is linear, so its level sets are straight lines (in 2D) or planes. Slide a line in the direction of increasing profit until it is about to leave the polyhedron: the last point it touches is a vertex (or a whole edge, if the line is parallel to an edge, in which case both ends of the edge are also optimal).

This gives a simple, if slow, algorithm: list all vertices and pick the best one. A vertex in 2D is the intersection of two boundary lines that is also feasible. The x ≥ 0 and y ≥ 0 rules count as boundary lines too, so we have five lines in total.

Python Brute-force vertex enumeration

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.

You should see five feasible vertices, and (3, 1) wins with profit 11. With n variables and m constraints there can be as many as C(m+n, n) vertices, so enumeration explodes. The simplex method of the next lesson walks from vertex to vertex without listing them all.

LP duality

Strong duality is at its cleanest for LPs. The dual of the problem above is:

Text
minimize    bᵀy
subject to  Aᵀy ≥ c
            y ≥ 0

There is one dual variable y_i per primal constraint (it is the shadow price of that constraint), and one dual constraint per primal variable. For the workshop, the dual is min 4y₁ + 9y₂ + 3y₃ subject to y₁ + y₂ + y₃ ≥ 3, y₁ + 3y₂ ≥ 2, y ≥ 0.

The prices y = (2, 0, 1) found earlier are feasible (2 + 0 + 1 = 3 ≥ 3, 2 + 0 = 2 ≥ 2) and give the dual value 4·2 + 9·0 + 3·1 = 11, equal to the primal optimum. Because LP constraints are affine, no Slater condition is needed: whenever the primal has a finite optimum, so does the dual, and the values match.

Complementary slackness reads: y_i > 0 only if constraint i is tight. Paint has y₂ = 0 because it has slack.

Solving LPs with SciPy

scipy.optimize.linprog minimizes cᵀx subject to A_ub x ≤ b_ub, A_eq x = b_eq and bounds on x. It also tells you when the problem is hopeless, and there are exactly two ways an LP can fail:

  • Infeasible: no point satisfies all constraints (example: x ≤ 1 and x ≥ 2).
  • Unbounded: the objective can improve forever (example: maximize x with only x ≥ 0).
Python Optimal, infeasible and unbounded LPs

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 status codes are 0 for success, 2 for infeasible and 3 for unbounded.

Many real LPs have degenerate vertices, where more constraints are tight than needed. Degeneracy can make a solver take extra pivots but does not change the answer.

Modeling tips

  • Write the quantity you decide as variables with clear units (liters, hours, dollars).
  • If a rule says "at least", use ≥; flip signs if your solver wants ≤.
  • Absolute values and maxima can often be turned into LPs by adding a helper variable (for example, minimize t subject to -t ≤ x ≤ t to minimize |x|).
  • Always check the solution against the original words of the problem, not just the math.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Where is the optimum of a bounded LP found?

    A linear objective has no interior stationary point, so the best value is reached on the boundary, at a vertex.
  2. 2. How many dual variables does an LP with 5 constraints Ax ≤ b have?

    Each primal constraint gets one multiplier (its shadow price).
  3. 3. What does the LP solver report for 'maximize x subject to x ≥ 0'?

    The objective grows without limit as x increases, and nothing forbids it.
  4. 4. Why is no Slater condition needed for LP strong duality?

    For affine inequality constraints, plain feasibility is enough, so a finite optimum always has a matching dual optimum.

Summary

  • An LP has a linear objective and linear constraints; its feasible set is a polyhedron.
  • The optimum of a bounded LP is at a vertex; enumeration works for tiny problems only.
  • The dual LP has one variable per constraint, and its optimum equals the primal optimum (strong duality, no extra condition).
  • A solver can return optimal, infeasible or unbounded.

Next: The Simplex Method from Scratch