Primer: linear and integer programming

Read first

• Primer A: graphs. Stops are nodes, legs are edges, and each edge has a weight, its distance. A distance matrix lists every weight. In this primer each edge also gets a yes/no decision: is this leg part of the plan?

The question this primer answers: how do you write a planning problem as equations, why does dropping “whole numbers only” make it easy to solve, and what does the easy version tell you about the hard one?

Intuition

A fleet for tomorrow

Start with a problem small enough to draw. Tomorrow I must deliver 14 crates to 21 stops. I can hire vans and cargo bikes:

Write x for the number of vans and y for the number of bikes. These are the decision variables. The plan must carry every crate and reach every stop, and it should cost as little as possible:

minimize    5x + 3y          (cost)
subject to  6x + 2y ≥ 14     (crates)
            4x + 6y ≥ 21     (stops)
            x ≥ 0,  y ≥ 0

The first line is the objective, the rest are constraints. Everything is linear: no products of variables, no squares. That makes it a linear program (LP).

Each constraint cuts the plane along a straight line and keeps one side. What is left is the feasible region, the set of plans that satisfy every constraint. Step through it below. The points are positions on a grid, with vans across and bikes up, not stops on a map.

The cost is lowest at a corner. That is no accident: the objective is a straight line too, and sliding it downhill over the region, the last point it touches is a corner (or a whole edge, in a tie). So an LP only needs to look at corners:

The simplex method walks from corner to corner, always downhill, and stops at a corner with no downhill edge. Along the crate line, y = 7 − 3x, so the cost is 5x + 3(7 − 3x) = 21 − 4x: downhill as x grows. Along the stop line the cost is 10.5 + 3x: uphill as x grows. X is where the two meet.

Whole vehicles

The LP says 1.5 vans and 2.5 bikes. Nobody hires half a van. Adding “x and y must be whole numbers” makes it an integer program (IP). The points around X tell the story:

Rounding the LP answer up gives 19, but the best whole plan is 17, and rounding never finds it. The LP optimum, 15, is still useful: no whole plan can beat it, because whole plans are a subset of all plans. Dropping the whole-number requirement is called the LP relaxation, and its value is a lower bound on the IP. The difference between 17 and 15 is the integrality gap.

The eight stops

The same ideas carry over to routing. Take the eight stops used throughout the series, with the distances below in units of 100 m; the optimal tour A-B-C-D-H-E-F-G-A costs 315.

Post 6 gives every directed leg a variable x(i, j), 1 if the plan drives from i to j and 0 if not, and asks each stop to be left once and entered once. Relaxing that to “any value between 0 and 1” and solving the LP gives the plan below: every stop paired with its nearest neighbour, and back.

It costs 282, a lower bound on 315. Here the LP happens to land on whole numbers, but the answer is four little loops, not a tour. Adding the constraints that forbid such loops raises the LP to 315 (Post 6). The art of integer programming is writing constraints so that the LP bound is as close to the true optimum as possible.

The formal idea

An LP with n variables x₁, …, xₙ and m constraints is

minimize    c₁x₁ + c₂x₂ + … + cₙxₙ
subject to  aᵢ₁x₁ + aᵢ₂x₂ + … + aᵢₙxₙ ≥ bᵢ     for each constraint i = 1, …, m
            xⱼ ≥ 0                            for each variable j = 1, …, n

The cⱼ are costs, the aᵢⱼ say how much of requirement i one unit of variable j provides, and the bᵢ are the requirements. In the fleet problem, n = 2, m = 2, c = (5, 3), b = (14, 21).

Corners. If an LP has an optimum, one of its corners is optimal. A corner is where n of the constraint boundaries meet, and there are finitely many, so the problem is a finite search. Dantzig invented the simplex method in 1947 to do that search efficiently.

flowchart TD
  S["Start at a corner"] --> P["Price each edge leaving it"]
  P --> Q{"Any edge goes downhill?"}
  Q -- yes --> W["Walk to the next corner"]
  W --> P
  Q -- no --> O["Optimal corner"]

Duality. Every LP has a partner, its dual. Put a price yᵢ ≥ 0 on each requirement. If no vehicle is worth more than it costs at those prices, the prices are dual feasible:

maximize    b₁y₁ + b₂y₂ + … + bₘyₘ
subject to  a₁ⱼy₁ + a₂ⱼy₂ + … + aₘⱼyₘ ≤ cⱼ     for each variable j
            yᵢ ≥ 0

For the fleet, a crate price u and a stop price v must satisfy 6u + 4v ≤ 5 for the van and 2u + 6v ≤ 3 for the bike. Any such prices give a lower bound 14u + 21v on the cost of every plan (weak duality). The best prices give exactly the LP optimum (strong duality: von Neumann described it to Dantzig in 1947, and Gale, Kuhn and Tucker published a proof in 1951). Here both vehicles are used at X, so both dual constraints are tight:

These are shadow prices. One more crate tomorrow raises the cheapest LP plan by 9/14 of ₹1,000, about ₹643; one more stop by 2/7, about ₹286.

Reduced costs. The reduced cost of variable j is its cost minus what it is worth at the shadow prices:

reduced cost of j  =  cⱼ − (a₁ⱼy₁ + a₂ⱼy₂ + … + aₘⱼyₘ)

At an optimum of a minimization LP, no variable has a negative reduced cost. If one does, bringing it in lowers the cost: that is the downhill edge the simplex looks for. At corner P, with only the crate rule tight, the price of a crate is 3/2 (a bike, 2 crates, costs 3), and the van’s reduced cost is 5 − 6 · 3/2 = −4: exactly the slope of 21 − 4x above.

Reduced costs also price variables you have not written down yet. A cargo trike carrying 4 crates to 4 stops for ₹3,500 has reduced cost 3.5 − (4 · 9/14 + 4 · 2/7) = −3/14, so adding it would lower the LP cost. Concorde uses this to add missing edges to its LP (Post 7), and exact VRP solvers use it to generate whole routes on demand (Post 39: Exact methods for VRP).

Integer programs. An IP adds “xⱼ must be a whole number” to some or all variables. Solving IPs is NP-hard in general, while LPs can be solved in polynomial time. Solvers bridge the two with the LP relaxation:

flowchart TD
  IP["Integer program"] --> R["Drop 'whole numbers only'"]
  R --> LP["Solve the LP relaxation"]
  LP --> B["Its value is a lower bound"]
  B --> Q{"LP solution all whole numbers?"}
  Q -- yes --> D["Also optimal for the IP"]
  Q -- no --> M{"Close the gap"}
  M -- branch --> BB["Branch and bound: Post 5"]
  M -- cut --> C["Cutting planes: Post 7"]

Land and Doig (1960) introduced LP-based branch and bound, which modern integer programming solvers still build on.

Common misconceptions

“Round the LP solution and you have the integer optimum.” In the fleet problem, rounding (1.5, 2.5) up gives a plan costing 19; the best whole plan, (1, 4), costs 17. Rounding down breaks both constraints. In the TSP, a fractional LP solution may not even suggest a tour.

“The LP relaxation is just a rough approximation.” It is a proven lower bound, and sometimes an exact one. The degree-only LP on the eight stops returns whole numbers because of the structure of the assignment problem: every corner of its feasible region is a whole-number assignment (Birkhoff 1946). And on berlin52, the LP with subtour constraints is exactly 7,542, the optimum (Post 6).

“The simplex method is exponential, so LPs are hard.” Klee and Minty (1972) built LPs on which a standard simplex rule visits all 2ⁿ corners. But on practical LPs the simplex method needs far fewer steps, and Khachiyan (1979) proved that LPs can be solved in polynomial time. The hard part is the integers.

Try it in Python

The script solves the fleet LP by listing every corner exactly, with fractions, then checks every whole-number plan in a box large enough to contain the best one, and finally computes the shadow prices and two reduced costs. Standard library only.

from fractions import Fraction
from itertools import combinations

# Tomorrow's fleet: x vans and y cargo bikes. Each rule reads a·x + b·y ≥ rhs.
rules = {
    "crates": (6, 2, 14),   # a van carries 6 crates, a bike 2; 14 crates to deliver
    "stops": (4, 6, 21),    # a van makes 4 stops, a bike 6; 21 stops to visit
    "x ≥ 0": (1, 0, 0),
    "y ≥ 0": (0, 1, 0),
}
COST = {"van": 5, "bike": 3}  # cost per vehicle per day, in ₹1,000

def cost(x, y):
    return COST["van"] * x + COST["bike"] * y

def feasible(x, y):
    return all(a * x + b * y >= rhs for a, b, rhs in rules.values())

# 1. Corners: where two rule boundaries meet and every rule holds.
corners = set()
for (a1, b1, r1), (a2, b2, r2) in combinations(rules.values(), 2):
    det = a1 * b2 - a2 * b1
    if det != 0:  # the two boundary lines cross at one point
        x, y = Fraction(r1 * b2 - r2 * b1, det), Fraction(a1 * r2 - a2 * r1, det)
        if feasible(x, y):
            corners.add((x, y))
for x, y in sorted(corners):
    print(f"corner ({float(x):g}, {float(y):g}): cost {float(cost(x, y)):g}")
lp_x, lp_y = min(corners, key=lambda p: cost(*p))
print(f"LP optimum: x = {lp_x}, y = {lp_y}, cost {cost(lp_x, lp_y)}")

# 2. Whole vehicles only: check every integer point in a box that is big enough.
whole = [(x, y) for x in range(9) for y in range(9) if feasible(x, y)]
ip_x, ip_y = min(whole, key=lambda p: cost(*p))
up_x, up_y = -(-lp_x // 1), -(-lp_y // 1)  # round both up
print(f"rounded up: ({up_x}, {up_y}), cost {cost(up_x, up_y)}")
print(f"integer optimum: ({ip_x}, {ip_y}), cost {cost(ip_x, ip_y)}")
gap = (cost(ip_x, ip_y) - cost(lp_x, lp_y)) / cost(ip_x, ip_y)
print(f"LP bound is {float(gap):.1%} below the integer optimum")

# 3. Duality: a price u per crate and v per stop that makes both vehicles break even.
#    At the LP optimum both vehicles are used, so 6u + 4v = 5 (van) and 2u + 6v = 3 (bike).
det = 6 * 6 - 4 * 2
u = Fraction(5 * 6 - 4 * 3, det)
v = Fraction(6 * 3 - 2 * 5, det)
print(f"shadow prices: crate {u}, stop {v}; dual value 14u + 21v = {14 * u + 21 * v}")

# 4. Reduced cost of a vehicle type we do not have yet: its cost minus what it is worth at those prices.
for name, crates, stops, price in (("car", 3, 3, Fraction(3)), ("trike", 4, 4, Fraction(7, 2))):
    reduced = price - (crates * u + stops * v)
    print(f"{name}: reduced cost {reduced} ({float(reduced):+.2f})")

It prints:

The dual value equals the LP optimum, as strong duality promises. The car’s positive reduced cost says it would never be used; the trike’s negative one says it would. An LP solver confirms it: with the trike available, the LP cost falls from 15 to 14.44.

Exercise

Suppose tomorrow brings 15 crates instead of 14, with everything else unchanged. Find the new corner where the crate and stop lines meet, and its cost. How much did the cost go up, and which number from this primer predicted it?

Hint: solve 6x + 2y = 15 and 4x + 6y = 21 together, for example by multiplying the first equation by 3 and subtracting the second. Then compare the increase with the shadow price of a crate.

Where to go next

• Post 5: Branch and bound: how a search tree uses lower bounds, the LP relaxation’s main job.
• Post 6: Integer programming formulations: the TSP as an IP, and why one formulation’s LP bound is far stronger than another’s.
• Post 7: Branch-and-cut and Concorde: adding constraints only when the LP breaks them, and pricing missing edges with reduced costs.
• Primer D: probability and statistics: the next primer, for the randomized methods of Parts 5 and 6.

References

• Kantorovich, L. V. (1939). Mathematical Methods of Organizing and Planning Production. Leningrad University. English translation: Management Science 6(4): 366–422, 1960.
• Birkhoff, G. (1946). “Tres observaciones sobre el álgebra lineal.” Universidad Nacional de Tucumán, Revista Serie A 5: 147–151.
• Dantzig, G. B. (1951). “Maximization of a Linear Function of Variables Subject to Linear Inequalities.” In Koopmans, T. C. (ed.), Activity Analysis of Production and Allocation, Wiley, 339–347.
• Gale, D., Kuhn, H. W., and Tucker, A. W. (1951). “Linear Programming and the Theory of Games.” In Koopmans, T. C. (ed.), Activity Analysis of Production and Allocation, Wiley, 317–329.
• Land, A. H., and Doig, A. G. (1960). “An Automatic Method of Solving Discrete Programming Problems.” Econometrica 28(3): 497–520.
• Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press.
• Klee, V., and Minty, G. J. (1972). “How Good Is the Simplex Algorithm?” In Shisha, O. (ed.), Inequalities III, Academic Press, 159–175.
• Khachiyan, L. G. (1979). “A Polynomial Algorithm in Linear Programming.” Doklady Akademii Nauk SSSR 244(5): 1093–1096.
• Chvátal, V. (1983). Linear Programming. W. H. Freeman.
• Wolsey, L. A. (2020). Integer Programming, 2nd ed. Wiley.

See the whole series · ← All writing