The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Combinatorial Optimization Algorithms

Next ►
►

In the previous lesson, Rutalia decided how many van and bike hours to hire: continuous variables, a smooth feasible region, an exact solver in milliseconds. But most of the warehouse's daily decisions aren't like that. Which packages do I load into this 100 kg van? In what order does the courier visit their 10 addresses? How many vans do I need, at minimum, to get all of today's orders out the door? There are no fractions here: each package either goes or it doesn't, each address occupies one position or another in the route. The solution space is discrete and, above all, explosive. This lesson introduces combinatorial optimization: its three canonical problems in Rutalia form (knapsack, traveling salesman, and bin packing), when a greedy algorithm suffices and when it deceives us, and what it means in practice for a problem to be NP-hard.

Contents

  1. What makes optimization "combinatorial"
  2. The combinatorial explosion, in numbers
  3. The 0/1 knapsack: loading a van
  4. The traveling salesman problem (TSP): ordering the courier's route
  5. Bin packing: how many vans do I need?
  6. Greedy algorithms: when they shine and when they fail
  7. NP-hardness for engineers: exact or approximate?

What makes optimization "combinatorial"

An optimization problem is combinatorial when its solutions are discrete objects — subsets, permutations, assignments — rather than real numbers. The three pieces from 02-01 are still there, but they change shape:

Piece In LP (02-01) In combinatorial optimization
Decision variables Real numbers (x = 10.5 hours) Yes/no decisions, orderings, groupings
Solution space Continuous polygon (infinitely many points, but "smooth") Finite yet gigantic set of combinations
Geometric tool The optimum lies at a vertex No geometry to save us: we have to search

The irony is delicious: the continuous space was infinite and we solved it exactly in milliseconds; the discrete space is finite and we often can't even dream of traversing it. The reason is that "finite" and "tractable" are not the same thing.

The combinatorial explosion, in numbers

Let's revisit the hierarchy table from 01-01, now applied to solution spaces. Suppose a machine capable of evaluating 100 million solutions per second (10⁸, generous for Python):

n Subsets (2ⁿ) Time Permutations (n!) Time
10 1,024 instant 3,628,800 0.04 s
15 32,768 instant ≈ 1.3 · 10¹² ≈ 3.6 hours
20 ≈ 10⁶ 0.01 s ≈ 2.4 · 10¹⁸ ≈ 770 years
30 ≈ 10⁹ 10 s ≈ 2.7 · 10³² ≈ 8 · 10¹⁶ years
50 ≈ 10¹⁵ 130 days ≈ 3 · 10⁶⁴ age of the universe × 10⁴⁷

Two practical takeaways:

  • Choosing subsets (which packages do I load?) grows as 2ⁿ: brutal, but it holds up to n ≈ 25-30 by brute force.
  • Choosing orderings (in what sequence do I deliver?) grows as n!: it dies somewhere between n = 12 and n = 15.

This explains the structure of the rest of the module: brute force today (to understand the problems), smart pruning in 02-03 (to reach further while keeping the optimality guarantee), and metaheuristics in 02-04/02-05 (for when even pruning isn't enough).

The 0/1 knapsack: loading a van

The problem at Rutalia. A van holds 15 units of load (normalized weight). There are 5 pending shipments; each has a weight and a value (what Rutalia bills for delivering it today). Which subset do I load to maximize revenue without exceeding capacity?

Shipment Weight Value (€)
E1 12 40
E2 7 24
E3 11 35
E4 8 26
E5 9 30

Formulation. Binary variables xᵢ ∈ {0, 1} (I load shipment i or I don't). Maximize Σ valueᵢ·xᵢ subject to Σ weightᵢ·xᵢ ≤ 15. It is exactly an integer linear program like those of 02-01 — with the extra restriction that the variables can only take the values 0 or 1. Hence the name 0/1 knapsack: each item goes in whole or not at all.

Solution by dynamic programming. Here we harvest what we sowed in 01-03: the problem has overlapping subproblems and optimal substructure. We define best[i][c] = maximum value using only the first i shipments with capacity c. For each shipment there are only two options — take it or leave it — and both refer back to smaller subproblems:

def knapsack_01(weights, values, capacity):
    n = len(weights)
    # best[i][c] = maximum value using shipments 0..i-1 with capacity c
    best = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        weight, value = weights[i - 1], values[i - 1]
        for c in range(capacity + 1):
            best[i][c] = best[i - 1][c]            # option A: don't load shipment i
            if weight <= c:                         # option B: load it (if it fits)
                with_it = best[i - 1][c - weight] + value
                best[i][c] = max(best[i][c], with_it)

    # Reconstruct the solution (as in 01-03: walk the table backwards)
    chosen, c = [], capacity
    for i in range(n, 0, -1):
        if best[i][c] != best[i - 1][c]:            # shipment i made the difference
            chosen.append(i - 1)
            c -= weights[i - 1]
    return best[n][capacity], sorted(chosen)

weights = [12, 7, 11, 8, 9]
values  = [40, 24, 35, 26, 30]
print(knapsack_01(weights, values, 15))   # (50, [1, 3])  → E2 + E4: weight 15, value €50

Points worth digesting slowly:

  • The optimal answer is E2 + E4 (weight 7+8 = 15, value €50). Notice that it does not include E1, the single most valuable shipment: loading it (weight 12) would leave only 3 free units — not enough for anything else.
  • The cost is Θ(n·C) in time and space (n shipments, C capacity). For n = 5, C = 15 that's a table of 96 cells; for n = 1,000 and C = 100,000 it's 10⁸ cells — big, but polynomial in appearance. Hold on to this nuance: we'll return to it in the NP-hardness section.
  • The backward reconstruction is the same technique we used in 01-03 to recover the minimum-cost path on the grid: the table stores values, and the decisions are deduced by comparing cells.

The traveling salesman problem (TSP): ordering the courier's route

The problem at Rutalia. A courier leaves the depot, visits 9 delivery points exactly once each, and returns to the depot. In what order should they be visited to minimize total kilometers? This is the Traveling Salesman Problem (TSP), probably the most famous combinatorial problem in the world.

Let's define the concrete instance we will use for the rest of the module (we'll solve it by brute force today, by branch and bound in 02-03, and with metaheuristics in 02-04 and 02-05, comparing results). Each point has coordinates in km on the city grid (the same grid from 01-03), and we use straight-line distance as a simplification:

import math

POINTS = {
    "DEP": (0, 0),                     # Rutalia's central depot
    "A": (2, 9), "B": (5, 4), "C": (7, 8), "D": (1, 5),
    "E": (8, 2), "F": (4, 7), "G": (9, 6), "H": (3, 1), "I": (6, 10),
}
NAMES = list(POINTS)                   # ["DEP", "A", ..., "I"]

def distance(a, b):
    (x1, y1), (x2, y2) = POINTS[a], POINTS[b]
    return math.hypot(x1 - x2, y1 - y2)

# Distance matrix: D[i][j] = km between point i and point j
D = [[distance(a, b) for b in NAMES] for a in NAMES]

Formulation. A solution is a permutation of the 9 delivery points (the depot fixes the start and the end). The cost of a route is the sum of consecutive distances, closing the cycle back to the depot. There are 9! = 362,880 permutations. Side note: in a closed tour, every route and its reverse have the same length, so there are really 9!/2 distinct routes; we won't exploit that detail in the code, to keep it simple.

Brute force. With 9 points we can still afford the luxury of looking at all of them:

from itertools import permutations

def route_length(route):
    """Route = tuple of indices starting with 0 (DEP). Sums the full cycle."""
    total = 0.0
    for i in range(len(route)):
        j = (i + 1) % len(route)       # the last leg returns to the depot
        total += D[route[i]][route[j]]
    return total

def tsp_brute_force():
    best_route, best_km = None, float("inf")
    for perm in permutations(range(1, len(NAMES))):   # permute points 1..9
        route = (0,) + perm                            # the depot always comes first
        km = route_length(route)
        if km < best_km:
            best_km, best_route = km, route
    return best_km, [NAMES[i] for i in best_route]

print(tsp_brute_force())
# (35.22, ['DEP', 'D', 'A', 'F', 'I', 'C', 'G', 'E', 'B', 'H'])

The optimum is 35.22 km, with the route DEP → D → A → F → I → C → G → E → B → H → DEP (there is another tied route that swaps the order of A and F; ties are common in geometric instances). On an ordinary laptop, Python evaluates the 362,880 permutations in a few seconds. But look back at the table in section 2: with 15 delivery points it would take hours; with 20, centuries. And a real Rutalia van makes 60-120 stops a day. Brute force serves us today for two things: understanding the problem, and giving us the correct answer for this instance (35.22 km), which will be the yardstick for the algorithms of the next three lessons.

Bin packing: how many vans do I need?

The problem at Rutalia. Today there are 12 orders with weights [6, 5, 8, 3, 7, 4, 2, 9, 5, 4, 6, 3] and every van carries at most 15. What is the minimum number of vans needed to carry everything? This is bin packing: packing items into the minimum number of fixed-capacity containers.

Unlike the knapsack (one container, maximize value), here we must cover all the items while minimizing containers. It is NP-hard, but it admits simple greedy heuristics with provable quality. The most widely used is First Fit Decreasing (FFD): sort the orders from largest to smallest and place each one in the first van where it fits (opening a new one if it fits in none):

def first_fit_decreasing(weights, capacity):
    vans = []                                 # each van = list of loaded weights
    for weight in sorted(weights, reverse=True):  # big orders first
        for load in vans:
            if sum(load) + weight <= capacity:
                load.append(weight)           # fits in an already-open van
                break
        else:                                 # the for's else: fit in none
            vans.append([weight])             # open a new van
    return vans

orders = [6, 5, 8, 3, 7, 4, 2, 9, 5, 4, 6, 3]
for i, v in enumerate(first_fit_decreasing(orders, 15), 1):
    print(f"Van {i}: {v}  (load {sum(v)}/15)")
# Van 1: [9, 6]           (load 15/15)
# Van 2: [8, 7]           (load 15/15)
# Van 3: [6, 5, 4]        (load 15/15)
# Van 4: [5, 4, 3, 3]     (load 15/15)
# Van 5: [2]              (load 2/15)

FFD uses 5 vans. Is that optimal? The total weight is 62, and 62 / 15 = 4.13..., so at least 5 vans are needed (4 vans would carry at most 60). That quick calculation — solution cost ≥ sum/capacity — is our first lower bound, a concept that will take absolute center stage in 02-03. Here the heuristic matches the bound, and therefore we know it is optimal without having explored anything. When they don't match, a band of uncertainty remains; for FFD it has been proven that it never uses more than 11/9 · OPT + 6/9 containers, an approximation guarantee: maybe not optimal, but never a disaster.

Greedy algorithms: when they shine and when they fail

FFD is an example of a greedy algorithm: it builds the solution step by step, taking at each moment the locally most promising decision and never reconsidering it. Cheap (usually Θ(n log n) because of the sort) and easy to write, greedy algorithms are the first temptation for any combinatorial problem. The critical question is: when does the best local decision lead to the global optimum?

When they work: fractional knapsack

If shipments could be split (bulk goods: sand, parcel freight consolidated by the kilo), the greedy by density value/weight is provably optimal: fill the van with the best €/kg, then the next, and split the last one that doesn't fit whole.

def fractional_knapsack(weights, values, capacity):
    by_density = sorted(range(len(weights)),
                        key=lambda i: values[i] / weights[i], reverse=True)
    total, free = 0.0, capacity
    for i in by_density:
        take = min(weights[i], free)         # whole if it fits; otherwise the fraction
        total += values[i] * (take / weights[i])
        free -= take
        if free == 0:
            break
    return total

print(fractional_knapsack([12, 7, 11, 8, 9], [40, 24, 35, 26, 30], 15))  # 51.0

The optimality argument (an exchange argument): if an optimal solution carried a kilo of worse goods while a better kilo was available, swapping them would improve it — contradiction. Divisibility makes that swap always possible.

When they work: canonical coin change

Making 68 cents of change with euro coins {50, 20, 10, 5, 2, 1} greedily (always the largest possible coin) gives 50+10+5+2+1 = 5 coins, and it's optimal. Real monetary systems are designed so that the greedy works (they're called canonical systems).

When they fail: 0/1 knapsack

Back to the indivisible van, with this minimal counterexample (capacity 10):

Shipment Weight Value Density €/kg
X 6 48 8.0
Y 5 35 7.0
Z 5 35 7.0

The greedy by density loads X (the best density)… and now neither Y nor Z fits (4 units of capacity remain). Result: €48. The optimum is Y+Z: €70. The locally perfect decision ruined the global one, because with shipments that can't be split, choosing X blocks the remaining capacity. Curiously, on our 5-shipment instance the greedy by density gets it right: it takes E2 (density 3.43), discards E1 and E5 because they no longer fit, and finishes with E4 → E2+E4 = €50, the optimum. Moral: a greedy getting one instance right proves nothing; a greedy failing on one instance (like X/Y/Z) proves it is not correct in general.

When they fail: non-canonical coins

With the system {1, 3, 4} and amount 6, the greedy gives 4+1+1 (3 coins); the optimum is 3+3 (2 coins). Same algorithm, different system, suboptimal result — the correctness of a greedy depends delicately on the structure of the problem, not on the general idea.

Operational summary: a greedy is a candidate for a solution, not a solution. Use it if (a) you can prove it's optimal (exchange arguments, matroids), (b) it has a known approximation guarantee (like FFD), or (c) you only need a decent initial solution — in fact, that's how we'll use it in 02-03 to kick off branch and bound with a good bound.

NP-hardness for engineers: exact or approximate?

0/1 knapsack, TSP, and bin packing are NP-hard. Without going into the formalism (NP classes, reductions — we don't need it here), what it means for you as an engineer is this:

  • Nobody knows an algorithm that solves all their instances in polynomial time, and the dominant conjecture (P ≠ NP) is that none exists. It's not that "we just haven't thought of it yet": there's been a million-dollar prize waiting for decades.
  • It does not mean every instance is intractable. Our knapsack was solved exactly with DP in Θ(n·C) — the trick is that this cost depends on the numeric value of the capacity, not just on the number of items (it's called a pseudo-polynomial cost: if C has 15 digits, you're lost, but with moderate capacities the DP flies). And the 10-node TSP fell to brute force.
  • The practical decision in the face of an NP-hard problem follows more or less this tree:
flowchart TD
    A["NP-hard combinatorial problem"] --> B{"Small instance?<br/>(problem-dependent:<br/>TSP ≲ 15-20, subsets ≲ 25)"}
    B -- "Yes" --> C["Exact by enumeration<br/>or better: with pruning (02-03)"]
    B -- "No" --> D{"Exploitable structure?<br/>(small capacities,<br/>special cases)"}
    D -- "Yes" --> E["Specialized exact method:<br/>pseudo-polynomial DP,<br/>ILP solvers"]
    D -- "No" --> F{"Do you need a<br/>quality guarantee?"}
    F -- "Yes" --> G["Approximation algorithm<br/>with a proven bound (e.g. FFD)"]
    F -- "No" --> H["Metaheuristics:<br/>genetic (02-04), ACO (02-05)"]
  • Bounds are your safety net. Even if you give up on the optimum, always compute a bound (like sum/capacity in bin packing): it tells you how much you might be losing. "My heuristic gives 5 and the lower bound is 5" is a free certificate of optimality; "it gives 9 and the bound is 5" is an invitation to keep working.

Common Mistakes and Tips

  • Underestimating the factorial. "It's only 20 stops" sounds innocent; that's 2.4 · 10¹⁸ possible orderings. Before writing itertools.permutations, compute math.factorial(n) and count its digits.
  • Trusting a greedy without hunting for a counterexample. Trying it on 3 instances and having it succeed is not a proof. Spend five minutes trying to break it (small instances, extreme values); if you can't, look up whether the problem has a known theoretical result.
  • Forgetting the return to the depot in the TSP. The classic mistake is summing only the outbound legs and picking a route that ends miles from the depot. Our route_length closes the cycle with the index (i + 1) % len(route).
  • Confusing knapsack with bin packing. Knapsack: one container, choose what goes in, maximize value. Bin packing: all the items go in, minimize containers. Applying the knapsack DP to bin packing makes no sense.
  • Ignoring that the knapsack DP is pseudo-polynomial. With capacity 10⁹ the table doesn't fit in memory. In that case: rescale units (do you really need gram precision?), or switch techniques.
  • Tip: always keep the best known solution and its bound. Everything we do in the next three lessons revolves around narrowing the gap between the two.

Exercises

  1. Knapsack by hand. A van of capacity 10; shipments with (weight, value): E1 (5, 21), E2 (4, 16), E3 (3, 12), E4 (6, 22). (a) Build the DP table best[i][c] by hand (5 rows × 11 columns) and find the optimal value and the chosen shipments. (b) What would the greedy by density have done? Does it get it right?

  2. Bin packing lower bound. Orders with weights [9, 8, 8, 7, 6, 6, 5, 5, 4, 2], capacity 15. (a) Compute the lower bound ⌈sum/capacity⌉. (b) Run FFD by hand. (c) Can you certify that FFD is optimal here? If FFD doesn't reach the bound, does that mean FFD failed?

  3. Breaking the TSP greedy. The natural TSP greedy is "nearest neighbor": from each point, always go to the closest unvisited point. Program it for our 10-point instance (use POINTS and D from the lesson, starting at DEP) and compare its kilometers against the 35.22 km optimum. What percentage overhead does it have?

Solutions

Exercise 1. (a) The table's last cell gives best[4][10] = 38, and the backward reconstruction selects E4 and E2. You can verify it by enumerating the feasible combinations (weight ≤ 10): E1+E2 → (9, €37), E1+E3 → (8, €33), E2+E3 → (7, €28), E2+E4 → (10, €38), E3+E4 → (9, €34); E1+E4 and any triple exceed capacity. Optimum: E2+E4, value €38 (it fills the van exactly). (b) Densities: E1 = 4.2; E2 = 4.0; E3 = 4.0; E4 ≈ 3.67. The greedy loads E1 (5 units of capacity left), then E2 (1 left), and nothing more fits → E1+E2 = €37. It misses by €1: it preferred E1's density and lost the E2+E4 combination that uses 100% of the capacity. A small failure, but a failure: the greedy is not correct for the 0/1 knapsack.

Exercise 2. (a) Sum = 60; ⌈60/15⌉ = 4. (b) FFD (already sorted from largest to smallest): 9→V1; 8→V2; 8→V3; 7→V2 (8+7=15); 6→V1 (9+6=15); 6→V3 (8+6=14); 5→V4; 5→V4 (10); 4→V4 (14); 2→V4 (16 doesn't fit)→V3 (14+2=16 doesn't fit)→V1, V2 full→ V5: [2]. Result: 5 vans. (c) The bound says ≥ 4 and FFD gives 5: we cannot certify optimality with this bound. And no, it doesn't mean FFD failed either: it may be that no 4-van solution exists (the lower bound is not always achievable). In fact here one does exist: [9,6] [8,7] [8,5,2] [6,5,4] = 4 vans filling 15+15+15+15 = 60. So FFD did end up one van above the optimum — consistent with its guarantee 11/9·OPT+6/9 ≈ 5.55. A double lesson: bounds bound, they don't decide; and heuristics with guarantees can still leave margin on the table.

Exercise 3.

def nearest_neighbor(start=0):
    route, visited = [start], {start}
    while len(route) < len(NAMES):
        current = route[-1]
        next_stop = min((j for j in range(len(NAMES)) if j not in visited),
                        key=lambda j: D[current][j])
        route.append(next_stop)
        visited.add(next_stop)
    return route, route_length(tuple(route))

route, km = nearest_neighbor()
print([NAMES[i] for i in route], round(km, 2))
# ['DEP', 'H', 'B', 'F', 'A', 'D', 'C', 'I', 'G', 'E'] 43.1

From DEP the nearest point is H (3.2 km), then B (3.6), then F (3.2), then A (2.8)… The greedy builds an excellent beginning and an expensive ending: the last points are left "orphaned" and force long legs (D→C at 6.7 km) plus a return to the depot of 8.2 km. Total: 43.1 km, a full 22% above the 35.22 km optimum. This is the general pattern of nearest neighbor: reasonable as an initial solution (we'll reuse it as a starting upper bound in 02-03), unacceptable as a final answer when kilometers cost money.

Conclusion

We have put names and faces on Rutalia's discrete decisions: 0/1 knapsack (what to load — solved exactly with the DP from 01-03), TSP (in what order to deliver — solved by brute force on our 10-point instance, with an optimum of 35.22 km we won't forget), and bin packing (how many vans — attacked with the FFD heuristic and certified with a lower bound). Along the way we learned that combinatorial spaces explode (2ⁿ, n!), that greedy algorithms are optimal only when the problem's structure allows it and treacherous when it doesn't, and that NP-hardness is not a death sentence but a usage manual: exact when you can, approximate with bounds when you can't. The TSP brute force looked at 362,880 routes to keep one; in the next lesson we'll learn to not look at the vast majority of them without losing the optimality guarantee: backtracking to discard the infeasible and branch and bound to discard whatever can no longer win. The bounds we used today to evaluate solutions will move on to steer the search.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved