Applications of Operations Research
Complete Exam Study Notes
Covering: Knapsack Problems · Bin Packing & Column Generation · Network Optimization · Clustering,
Facility Location & Scheduling · TSP · VRP · Metaheuristics
Topic Class
0-1 Knapsack Problem – Heuristics, Relaxations, Performance Guarantees 1
Other Knapsack Problems – Lagrangian Relaxation, Surrogate Relaxation 2
Bin Packing & Column Generation 3
Optimization Problems on Networks (Assignment, Shortest Path, MST, Steiner, VC) 4
Clustering, Facility Location & Scheduling 5
Traveling Salesperson Problem (TSP) 6
Vehicle Routing Problems (MTSP, VRP, VRPTW) 7
Case Study: Course Scheduling 8
Metaheuristics (VNS, Tabu Search, SA, Genetic Algorithms) 9
,1 0-1 Knapsack Problem
1.1 Problem Definition
Given n items with weights ai and utilities ci, and a knapsack with capacity b, choose a subset of items
maximising total utility without exceeding the capacity.
max Σ cixi s.t. Σ aixi ≤ b, xi ∈ {0,1}
Assumptions: n, b, ai, ci are positive integers; Σai > b (non-trivial); ai ≤ b for all i (each item can potentially fit).
• NP-hard problem: no known polynomial-time algorithm for all instances.
• Branch & bound: may need to evaluate 2n solutions in worst case.
• Dynamic programming: solves n·b subproblems — not efficient when b is large.
• Real-world examples: hiker packing, funding agency choosing projects, manufacturer selecting orders.
1.2 LP Relaxation & Rounding Heuristic
Replace xi ∈ {0,1} with 0 ≤ xi ≤ 1 → becomes a Linear Program (LP).
Optimal LP solution: Sort items by decreasing utility-to-weight ratio ci/ai. Fill capacity greedily; the last item that
partially fits is the critical item s.
Optimal LP: xi=1 for i=1,…,s−1; xs = b■/as (b■ = remaining capacity); xi=0 for i>s
Rounding heuristic: Round down the fractional value (set xs=0). Result is a feasible integer solution.
■ Rounding can be arbitrarily bad: e.g., item 1 (utility 2, weight 1) vs item 2 (utility 106, weight 106) with
b=106. Rounding gives value 2 vs optimal 106.
1.3 Greedy Heuristic
Sort items by decreasing utility. Fill knapsack greedily: add item if it fits, skip if not, continue.
■ The greedy heuristic can also be arbitrarily bad: n items, item 1 has utility 2 and weight n−1, items 2..n
each have utility 1 and weight 1, capacity=n−1. Greedy picks item 1 (value 2) vs optimal n−1.
1.4 Greedy 2.0 (Combined Heuristic) – Performance Guarantee of 2
Run both rounding heuristic (value zR) and greedy heuristic (value zG). Take the best: zG2 = max{zR, zG}.
Proof of performance guarantee:
• Let zLP = optimal LP value (has at most 1 fractional item, the critical item s).
• Rounding up all LP values gives zR + cs ≥ zLP ≥ zOPT.
• Also: cs ≤ zG (the critical item alone is a feasible solution for greedy).
• Therefore: zOPT ≤ zR + cs ≤ 2·max{zR, zG} = 2zG2.
■ Greedy 2.0 guarantees: zOPT ≤ 2·zG2 → solution is at least half optimal.
1.5 Relaxations & Dual Bounds
Relaxation R of problem P: R is a relaxation if its feasible region Y ⊇ X (larger) and its objective g(x) ≥ f(x) for
all x ∈ X (at least as good).
Key theorem: zR ≥ zP — the optimal value of a relaxation is an upper bound (for maximisation).
Proof of optimality via relaxation: If the relaxation's optimal solution xR is feasible for P and g(xR)=f(xR), then
xR is optimal for P.
Common relaxations for MIP:
• LP relaxation: replace xi∈{0,1} with 0≤xi≤1.
• Lagrangian relaxation: move a constraint into the objective with a penalty multiplier.
• Surrogate relaxation: aggregate multiple constraints into one.
, Dual bound: upper bound (maximisation) / lower bound (minimisation) obtained via a relaxation. Primal
bound: obtained from a feasible solution.
Gap: difference between dual bound and primal bound. Algorithm stops when gap is small enough.
1.6 Performance Guarantees
A heuristic has a performance guarantee of k if for every instance, the heuristic value is never worse than
OPT/k (maximisation) or k·OPT (minimisation).
• Rounding heuristic alone: no finite performance guarantee.
• Greedy heuristic alone: no finite performance guarantee.
• Greedy 2.0: performance guarantee of 2.
Note: Average performance is usually much better than worst-case guarantees.
Complete Exam Study Notes
Covering: Knapsack Problems · Bin Packing & Column Generation · Network Optimization · Clustering,
Facility Location & Scheduling · TSP · VRP · Metaheuristics
Topic Class
0-1 Knapsack Problem – Heuristics, Relaxations, Performance Guarantees 1
Other Knapsack Problems – Lagrangian Relaxation, Surrogate Relaxation 2
Bin Packing & Column Generation 3
Optimization Problems on Networks (Assignment, Shortest Path, MST, Steiner, VC) 4
Clustering, Facility Location & Scheduling 5
Traveling Salesperson Problem (TSP) 6
Vehicle Routing Problems (MTSP, VRP, VRPTW) 7
Case Study: Course Scheduling 8
Metaheuristics (VNS, Tabu Search, SA, Genetic Algorithms) 9
,1 0-1 Knapsack Problem
1.1 Problem Definition
Given n items with weights ai and utilities ci, and a knapsack with capacity b, choose a subset of items
maximising total utility without exceeding the capacity.
max Σ cixi s.t. Σ aixi ≤ b, xi ∈ {0,1}
Assumptions: n, b, ai, ci are positive integers; Σai > b (non-trivial); ai ≤ b for all i (each item can potentially fit).
• NP-hard problem: no known polynomial-time algorithm for all instances.
• Branch & bound: may need to evaluate 2n solutions in worst case.
• Dynamic programming: solves n·b subproblems — not efficient when b is large.
• Real-world examples: hiker packing, funding agency choosing projects, manufacturer selecting orders.
1.2 LP Relaxation & Rounding Heuristic
Replace xi ∈ {0,1} with 0 ≤ xi ≤ 1 → becomes a Linear Program (LP).
Optimal LP solution: Sort items by decreasing utility-to-weight ratio ci/ai. Fill capacity greedily; the last item that
partially fits is the critical item s.
Optimal LP: xi=1 for i=1,…,s−1; xs = b■/as (b■ = remaining capacity); xi=0 for i>s
Rounding heuristic: Round down the fractional value (set xs=0). Result is a feasible integer solution.
■ Rounding can be arbitrarily bad: e.g., item 1 (utility 2, weight 1) vs item 2 (utility 106, weight 106) with
b=106. Rounding gives value 2 vs optimal 106.
1.3 Greedy Heuristic
Sort items by decreasing utility. Fill knapsack greedily: add item if it fits, skip if not, continue.
■ The greedy heuristic can also be arbitrarily bad: n items, item 1 has utility 2 and weight n−1, items 2..n
each have utility 1 and weight 1, capacity=n−1. Greedy picks item 1 (value 2) vs optimal n−1.
1.4 Greedy 2.0 (Combined Heuristic) – Performance Guarantee of 2
Run both rounding heuristic (value zR) and greedy heuristic (value zG). Take the best: zG2 = max{zR, zG}.
Proof of performance guarantee:
• Let zLP = optimal LP value (has at most 1 fractional item, the critical item s).
• Rounding up all LP values gives zR + cs ≥ zLP ≥ zOPT.
• Also: cs ≤ zG (the critical item alone is a feasible solution for greedy).
• Therefore: zOPT ≤ zR + cs ≤ 2·max{zR, zG} = 2zG2.
■ Greedy 2.0 guarantees: zOPT ≤ 2·zG2 → solution is at least half optimal.
1.5 Relaxations & Dual Bounds
Relaxation R of problem P: R is a relaxation if its feasible region Y ⊇ X (larger) and its objective g(x) ≥ f(x) for
all x ∈ X (at least as good).
Key theorem: zR ≥ zP — the optimal value of a relaxation is an upper bound (for maximisation).
Proof of optimality via relaxation: If the relaxation's optimal solution xR is feasible for P and g(xR)=f(xR), then
xR is optimal for P.
Common relaxations for MIP:
• LP relaxation: replace xi∈{0,1} with 0≤xi≤1.
• Lagrangian relaxation: move a constraint into the objective with a penalty multiplier.
• Surrogate relaxation: aggregate multiple constraints into one.
, Dual bound: upper bound (maximisation) / lower bound (minimisation) obtained via a relaxation. Primal
bound: obtained from a feasible solution.
Gap: difference between dual bound and primal bound. Algorithm stops when gap is small enough.
1.6 Performance Guarantees
A heuristic has a performance guarantee of k if for every instance, the heuristic value is never worse than
OPT/k (maximisation) or k·OPT (minimisation).
• Rounding heuristic alone: no finite performance guarantee.
• Greedy heuristic alone: no finite performance guarantee.
• Greedy 2.0: performance guarantee of 2.
Note: Average performance is usually much better than worst-case guarantees.
