Applications of Operation Research
Academic Year 2025 – 2026 Michael Jackson
Inhoudsopgave
1 0-1 Knapsack Problems 3
1.1 Introduction to the 0-1 Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Complexity and Exact Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Linear Programming (LP) Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Relaxations and Dual Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Heuristics and Performance Guarantees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5.1 Rounding Heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5.2 Greedy Heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5.3 Greedy 2.0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.6 Practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Session 2: Other Knapsack Problems 6
2.1 0-1 Knapsack Cover Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.1 Lagrangian Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 0-1 Multiple Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.1 Surrogate Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.2 Greedy Heuristics for Multiple Knapsacks . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 Session 3: Bin Packing Problem and Column Generation 11
3.1 The Bin Packing Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Heuristics for Bin Packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3 Alternative Modeling: The Pattern Formulation . . . . . . . . . . . . . . . . . . . . . . . . 12
3.4 Column Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.4.1 Initialization: Start Pattern Proposals . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.4.2 Dual Prices and the Pricing Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.5 From Fractional to Integer Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.6 Practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4 Session 4: Optimization Problems on Networks 16
4.1 Assignment Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2 Shortest Path Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.3 Minimum Spanning Tree (MST) Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.4 Steiner Tree Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.5 Vertex Cover Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.6 Practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5 Session 5: Clustering, Facility Location and Scheduling 20
5.1 Clustering and the k-Means Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.2 Uncapacitated Facility Location Problem (UFLP) . . . . . . . . . . . . . . . . . . . . . . . 21
5.3 Parallel Machine Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.4 Practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
,6 Session 6: Traveling Salesperson Problem 26
6.1 Introduction to the TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6.2 Subtour Elimination Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
6.3 Construction Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
6.4 Local Search for TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
6.5 The Symmetric TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
6.6 Real-World TSP: Amazon Last Mile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
7 Session 7: Vehicle Routing Problems 30
7.1 Multiple Traveling Salesperson Problem (MTSP) . . . . . . . . . . . . . . . . . . . . . . . 30
7.2 Alternative: The Route-Based Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . 30
7.3 The Vehicle Routing Problem (VRP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
7.4 Vehicle Routing Problem with Time Windows (VRPTW) . . . . . . . . . . . . . . . . . . 32
7.5 Practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
8 Session 8: Metaheuristics 33
8.1 Introduction: Escaping Local Optima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
8.2 Iterated Local Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
8.3 Variable Neighborhood Search (VNS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
8.4 Accept Non-Improving Neighbours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
8.4.1 TabuSearch (TS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
8.4.2 Simulated Annealing (SA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
8.5 Genetic Algorithms (GA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
8.5.1 The GA Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Definitions Theorems Example: Exercise:
Formulations Bounds and gua- Slide scenarios Conceptual
and core con- rantees. and proofs. questions.
cepts.
Applications of Operation Research
Michael Jackson 2/38
,1 0-1 Knapsack Problems
1.1 Introduction to the 0-1 Knapsack Problem
The 0-1 knapsack problem involves selecting a subset of n items to maximize utility without exceeding a
weight capacity b. Each item i has a weight ai and a utility ci .
Mathematical Formulation
The problem is modeled using binary decision variables xi → {0, 1}, where xi = 1 if item i is
chosen, and 0 otherwise.
n
!
max ci xi
i=1
!n
s.t. ai xi ↑ b
i=1
xi → {0, 1} i = 1, . . . , n
"
Assumptions: n, b, ai , ci are positive integers, ai ↑ b, and ai > b.
Example: The Graduation Gift Budget
You receive €10K. You must choose between indivisible alternatives (exotic trip, car, motorcycle,
etc.) to maximize happiness.
• Variables: x1 (Trip, cost: 4K, util: 4), x2 (Car, cost: 8K, util: 5), x3 (Motorcycle, cost:
3K, util: 4), x4 (Language, cost: 1K, util: 3), x5 (Party, cost: 1K, util: 2), x6 (Redecorate,
cost: 2K, util: 3).
• Constraint: 4x1 + 8x2 + 3x3 + 1x4 + 1x5 + 2x6 ↑ 10
1.2 Complexity and Exact Methods
The 0-1 knapsack problem is NP-hard. While exact methods like branch and bound or dynamic program-
ming can solve it, they are not e!cient in the worst case. Branch and bound may evaluate 2n solutions,
and dynamic programming solves nb subproblems.
1.3 Linear Programming (LP) Relaxation
If items are perfectly divisible, the problem becomes a linear program (LP). We replace the binary
constraint xi → {0, 1} with 0 ↑ xi ↑ 1.
Solution Method: Sort items in decreasing order of their e!ciency ratio acii . Fill the knapsack until
capacity is reached. The first item that does not fully fit is the critical item s, defined as s "
= min{j :
"j b→
s→1
ai
i=1 ai > b}. The optimal LP solution assigns xi = 1 for i < s, xi = 0 for i > s, and xs = i=1
as .
Example: LP Relaxation of the Graduation Gift
Sorting by ratio acii favors the Language (3/1), Party (2/1), Redecorate (3/2), and Motorcycle
(4/3). Taking these uses 7K of the 10K budget. The next best item is the Trip (4K). Because
it’s an LP relaxation, we can take a fraction of it: 10→7
4 = 3/4. The optimal LP solution is
(3/4, 0, 1, 1, 1, 1) yielding a utility of 15.
Applications of Operation Research
Michael Jackson 3/38
,1.4 Relaxations and Dual Bounds
To evaluate heuristics, we compare their solutions to bounds. A Primal Bound is a lower bound (for
maximization) obtained from any feasible solution. A Dual Bound is an upper bound obtained by
solving a relaxation (like the LP yielding 15 in the example above).
↓ Many optimization algorithms compute lower and upper bounds on the optimal value until the
di"erence, called the gap, is small enough.
Formal Definition of a Relaxation
Let original problem P be z P = maxx↑X f (x) and problem R be z R = maxx↑Y g(x). R is a
relaxation of P if:
1. X ↔ Y (the feasible region is expanded).
2. f (x) ↑ g(x) for all x → X (the objective is overestimated).
This guarantees that z P ↑ z R , meaning R provides a valid upper bound.
Objective Value
zR
zP
g(x)
f (x)
x
x↓
Expanded Feasible Region Y
Original Feasible Region X
Figuur 1: Relaxations like defined above
1.5 Heuristics and Performance Guarantees
When exact methods are too slow, we use heuristics to find good feasible solutions quickly.
1.5.1 Rounding Heuristic
Solve the LP relaxation and round down the fractional variable to 0.
Example: Worst-Case Rounding
Setup: Item 1 (c1 = 2, a1 = 1). Item 2 (c2 = 10, a2 = 10). Capacity b = 10.
• LP Solution: Item 1 is more e!cient (2/1 > 10/10). We take all of Item 1, leaving 9
capacity. We take 9/10 of Item 2.
• Rounding: Rounding down the fractional 9/10 leaves us with only Item 1 (utility 2).
• Optimal: Taking Item 2 (utility 10).
Applications of Operation Research
Michael Jackson 4/38
, If Item 2 had utility and weight of 106 , the rounding heuristic still gets 2, while optimal gets 106 .
The performance can be arbitrarily bad.
1.5.2 Greedy Heuristic
Sort items in non-increasing order of their utilities (ci ) and fill the knapsack. If an item doesn’t fit, skip
to the next.
Example: Worst-Case Greedy
Setup: We have n items. Item 1 has c1 = 2, a1 = n ↗ 1. Items 2 to n have ci = 1, ai = 1.
Capacity b = n ↗ 1.
• Greedy Solution: Item 1 has the highest utility (2), so greedy picks it. The knapsack is
now full. Total utility: 2.
• Optimal: Ignore Item 1 and pack all other items (2 to n). Total utility: n ↗ 1.
As n grows, the greedy heuristic remains stuck at 2, performing arbitrarily poorly.
1.5.3 Greedy 2.0
To overcome the arbitrary badness of the previous heuristics, Greedy 2.0 returns the best solution between
the Rounding heuristic (z R ) and the Greedy heuristic (z G ).
z G2 = max{z R , z G }
Performance Guarantee of 2
Greedy 2.0 has a performance guarantee of 2, meaning the optimal value z OP T is never more than
twice the heuristic value z G2 (z OP T ↑ 2z G2 ). Proof Sketch:
"n
1. z OP T ↑ z LP ↑ i=1 ci ↘xLPi ≃.
2. Since the LP solution has at"most one fractional variable, rounding it up adds at most the
maximum utility c↓ . Thus, i ≃↑z +c .
ci ↘xLP R ↓
3. We know c↓ ↑ z G (since the greedy heuristic checks the max utility item).
4. Therefore, z R + c↓ ↑ 2 max{z G , z R } = 2z G2 .
1.6 Practice
Exercise: 0-1 Knapsack Cover Problem
Problem Statement:
n
!
min ci xi
i=1
!n
s.t. ai xi ⇐ b
i=1
xi → {0, 1} i = 1, . . . , n
Questions for consideration:
• Notice the di"erence with the standard 0-1 knapsack problem.
• When does one need to solve a 0-1 knapsack cover problem?
Applications of Operation Research
Michael Jackson 5/38
, • How would you solve the LP relaxation? Can you propose a rounding heuristic and/or a
greedy heuristic?
2 Session 2: Other Knapsack Problems
2.1 0-1 Knapsack Cover Problem
Unlike the standard knapsack problem where we maximize utility under a capacity constraint, the knap-
sack cover problem aims to minimize cost while meeting or exceeding a certain demand constraint.
Example: Choice of Production Plants
Scenario: A company has n production plants and a known demand b. Plant i produces ai units
at a fixed cost ci . The goal is to choose which plants to run to satisfy demand at minimum cost.
n
!
min ci xi
i=1
!n
s.t. ai xi ⇐ b
i=1
xi → {0, 1} i = 1, . . . , n
2.1.1 Lagrangian Relaxation
Instead of dropping the tricky constraint entirely, we can move it to the objective function and penalize
its violation using a Lagrange multiplier ω ⇐ 0.
Lagrangian Relaxation
Let ω ⇐ 0 be the multiplier for the knapsack cover constraint. We define the relaxed problem as:
n
# n
$
! !
z(ω) = min ci xi + ω b ↗ ai xi s.t. xi → {0, 1}
i=1 i=1
Rewriting this makes it easily solvable by inspection:
n
!
z(ω) = ωb + min (ci ↗ ωai )xi
i=1
For each i, if ci ↗ ωai ↑ 0, we set xi = 1; otherwise, xi = 0. Thus:
n
!
z(ω) = ωb + min{ci ↗ ωai , 0}
i=1
The Lagrangian Dual Bound
To find the best lower bound provided by this relaxation, we solve the Lagrangian Dual problem:
z LD = max z(ω)
ω↔0
The Lagrangian dual bound cannot be worse than the LP bound. For this specific relaxation of
the 0-1 knapsack cover problem, z LD gives the exact same bound as the LP relaxation.
Applications of Operation Research
Michael Jackson 6/38
, Example: Evaluating the Bound
Setup: min 5x1 + 4x2 + 2x3 s.t. 2x1 + 3x2 + x3 ⇐ 5; x1 , x2 , x3 → {0, 1}
• LP Optimum: x1 = 1/2, x2 = 1, x3 = 1. Optimal LP value is 8.5. (IP optimal is 9).
• Lagrangian Function: z(ω) = 5ω + min{5 ↗ 2ω, 0} + min{4 ↗ 3ω, 0} + min{2 ↗ ω, 0}
Evaluating z(ω) across its breakpoints (4/3, 2, 5/2) gives a piecewise function. The maximum
value of this function occurs at ω → [4/3, 5/2] yielding z LD = max{20/3, 8, 8.5, 8.5} = 8.5. This
confirms it equals the LP bound!
2.2 0-1 Multiple Knapsack Problem
Here, we have m knapsacks (m < n) with di"erent capacities bj . Each item i can go into at most one
knapsack. We assume each item fits into every knapsack individually, but all items together exceed the
capacity of any single knapsack.
Example: Allocating Orders to Workers
Scenario: You manage m workers to fulfill n orders. Worker j can work for bj time units. Order
i takes ai time and brings ci profit.
!!
max ci xij
i↑N j↑M
!
s.t. xij ↑ 1 ⇒i → N (Each order done by at most 1 worker)
j↑M
!
ai xij ↑ bj ⇒j → M (Worker capacity constraint)
i↑N
xij → {0, 1}
2.2.1 Surrogate Relaxation
Surrogate Relaxation
Given positive multipliers ε1 , . . . , εm , we combine the m capacity constraints into a single cons-
traint: ! ! !
εj ai xij ↑ εj b j
j↑M i↑N j↑M
This creates a single knapsack constraint, providing an upper bound. If all εj are equal, it reduces
directly to a standard 0-1 knapsack problem. "Di"erent choices for εj yield di"erent upper bounds.
When all the εi are equal, and defining yi = j↑M xij , the relaxed problem is the same as
!
max ci yi
i↑N
! !
s.t. ai yi ↑ bj
i↑N j↑M
yi → {0, 1}; i→N
which is a 0-1 knapsack problem
Applications of Operation Research
Michael Jackson 7/38
,2.2.2 Greedy Heuristics for Multiple Knapsacks
Greedy Heuristic: Sort items by ci /ai ⇐ · · · ⇐ cn /an . Fill knapsack 1 until full, then move to knapsack
2, etc. The first item that does not fit in knapsack j is its critical item sj .
Performance Guarantee of Greedy 2.0
Let z G be the value from the standard greedy heuristic. Let csj be the utility of the critical item
for each knapsack j. Define Greedy 2.0’s value as:
!
z G2 = max z G , csj
j↑M
"
Because z G + csj is an upper bound on the LP relaxation of the surrogate relaxation, it also
bounds z OP T . Therefore: !
2z G2 ⇐ z G + csj ⇐ z OP T
j↑M
This guarantees Greedy 2.0 will always yield at least half the optimal value.
2.3 Practice
Exercise: 2-Dimensional Knapsack Problem
You have a bag limited by weight (b1 = 8) and volume (b2 = 10). Each object i has a value ci ,
weight a1i , and volume a2i .
max 4x1 + 3x2 + x3 + 6x4 + 5x5
s.t. x1 + 3x2 + 4x3 + 3x4 + 2x5 ↑ 8 (Weight)
8x1 + x2 + 9x3 + x5 ↑ 10 (Volume)
x1 , x2 , x3 , x4 , x5 → {0, 1}
1. Give a heuristic algorithm for this problem.
2. Propose an instance where your heuristic fails.
3. Apply your heuristic to this specific instance and evaluate the solution quality.
Solution:
1. Heuristic Design: For multidimensional knapsack problems, a greedy heuristic can be
constructed by sorting items according to a resource-weighted e!ciency ratio. Let the ratio
for item i be:
c
Ratioi = + i ,
max b1 , b2
a1i a2i
This penalizes items that consume a large fraction of your strictest bottleneck resource.
2. Failure Concept: Heuristics fail when they greedily lock in items that look highly e!cient
individually but consume resources in a way that blocks a superior combination of multiple
slightly lower-ranked items.
3. Application to Instance: Let’s calculate the bottleneck consumption ratio for each item:
• Item 1: max(1/8, 8/10) = 0.80 =⇑ Ratio1 = 4/0.8 = 5.0
• Item 2: max(3/8, 1/10) = 0.375 =⇑ Ratio2 = 3/0.375 = 8.0
Applications of Operation Research
Michael Jackson 8/38
, • Item 3: max(4/8, 9/10) = 0.90 =⇑ Ratio3 = 1/0.9 ⇓ 1.11
• Item 4: max(3/8, 0/10) = 0.375 =⇑ Ratio4 = 6/0.375 = 16.0
• Item 5: max(2/8, 1/10) = 0.25 =⇑ Ratio5 = 5/0.25 = 20.0
Sorting items by decreasing e!ciency yields the order: Item 5, Item 4, Item 2, Item 1,
Item 3.
Greedy Packing Strategy:
• Pack Item 5: Remaining Weight = 8 ↗ 2 = 6, Volume = 10 ↗ 1 = 9. Profit = 5.
• Pack Item 4: Remaining Weight = 6 ↗ 3 = 3, Volume = 9 ↗ 0 = 9. Profit = 5 + 6 = 11.
• Pack Item 2: Remaining Weight = 3↗3 = 0, Volume = 9↗1 = 8. Profit = 11+3 = 14.
• Item 1 and Item 3 no longer fit due to the weight capacity being completely exhausted.
Heuristic Solution: xHEU R = (0, 1, 0, 1, 1) with an objective value of 14.
Evaluation of Quality: The heuristic solution is sub-optimal. If we bypass Item 2 and
select Item 1 instead, we can construct the feasible bundle {1, 4, 5}. Total Weight = 1 +
3 + 2 = 6 ↑ 8. Total Volume = 8 + 0 + 1 = 9 ↑ 10. Optimal Solution: xOP T = (1, 0, 0, 1, 1)
with an objective value of 15.
Volume (a2 )
Capacity Bounds (8, 10)
I3 (1)
I1 (4) Optimal
Bundle
(I1+I4+I5)
= 15
Heuristic
Bundle
(I2+I4+I5)
= 14
I2 (3)
I5(5)I4 (6)
Weight (a1 )
Exercise: 1-Dimensional Cutting Stock Problem
Materials are supplied in master pieces of standard length L. There is a demand di for smaller
pieces of length li ↑ L. Goal: minimize the total number of master pieces needed to satisfy
demand.
1. Model the problem mathematically.
2. Develop a construction heuristic.
3. Give an explicit counterexample instance where the heuristic fails.
Applications of Operation Research
Michael Jackson 9/38
, 4. Find a heuristic with a performance guarantee of 2 using a waste argument.
Solution:
1. Mathematical Model (Kantorovich Formulation): Let " W be a conservative upper
bound on the number of master pieces needed (e.g., W = di ). Define binary variables
yj = 1 if master piece j is used, 0 otherwise. Define integer variables xij ⇐ 0 as the number
of times item i is cut from master piece j.
W
!
min yj
j=1
W
!
s.t. xij ⇐ di ⇒i = 1, . . . , n (Demand fulfillment)
j=1
!n
li xij ↑ Lyj ⇒j = 1, . . . , W (Length capacity constraint)
i=1
yj → {0, 1}, xij ⇐ 0 and integer
2. Construction Heuristic: First-Fit Decreasing (FFD). Sort all demanded items in
non-increasing order of their lengths. Iterate through the sorted items and place each one
into the first already-opened master piece that has enough remaining residual capacity. If it
fits nowhere, open a new master piece.
3. Counterexample Instance: Let master piece length L = 10. Suppose the total demand
consists of: two pieces of length 4 and four pieces of length 3.
Running the FFD heuristic (Sorted items: 4, 4, 3, 3, 3, 3):
• Bar 1: Packs the two 4s. Remaining capacity = 10 ↗ 4 ↗ 4 = 2. None of the remaining
pieces of length 3 can fit.
• Bar 2: Packs three 3s. Remaining capacity = 10 ↗ 3 ↗ 3 ↗ 3 = 1.
• Bar 3: Packs the final remaining piece of length 3.
FFD uses 3 bars. However, the optimal arrangement splits the pairs:
• Bar 1: One 4, two 3s (Total = 4 + 3 + 3 = 10). Remaining capacity = 0.
• Bar 2: One 4, two 3s (Total = 4 + 3 + 3 = 10). Remaining capacity = 0.
The true optimal solution requires only 2 bars. FFD fails.
4. Performance Guarantee of 2 (Next-Fit Waste Proof): Consider the simple Next-Fit
(NF) heuristic. NF packs items into the current master piece; when an item doesn’t fit, it
permanently closes that master piece and opens a new one.
Let M be the total number of bars used by Next-Fit. Consider any two consecutive bars j
and j + 1. Let Wj be the used capacity in bar j and Wj+1 the used capacity in bar j + 1.
Because the first item in bar j + 1 failed to fit into bar j, it must be true that:
Wj + (first item length in bar j + 1) > L =⇑ Wj + Wj+1 > L
Summing this inequality across all consecutive pairs of bars implies that the total combined
content of the occupied bars satisfies:
M ↗1
n
!
d i li > L
i=1
2
Applications of Operation Research
Michael Jackson 10/38
Academic Year 2025 – 2026 Michael Jackson
Inhoudsopgave
1 0-1 Knapsack Problems 3
1.1 Introduction to the 0-1 Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Complexity and Exact Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Linear Programming (LP) Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Relaxations and Dual Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Heuristics and Performance Guarantees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5.1 Rounding Heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5.2 Greedy Heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5.3 Greedy 2.0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.6 Practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Session 2: Other Knapsack Problems 6
2.1 0-1 Knapsack Cover Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.1 Lagrangian Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 0-1 Multiple Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.1 Surrogate Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.2 Greedy Heuristics for Multiple Knapsacks . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 Session 3: Bin Packing Problem and Column Generation 11
3.1 The Bin Packing Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Heuristics for Bin Packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3 Alternative Modeling: The Pattern Formulation . . . . . . . . . . . . . . . . . . . . . . . . 12
3.4 Column Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.4.1 Initialization: Start Pattern Proposals . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.4.2 Dual Prices and the Pricing Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.5 From Fractional to Integer Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.6 Practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4 Session 4: Optimization Problems on Networks 16
4.1 Assignment Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2 Shortest Path Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.3 Minimum Spanning Tree (MST) Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.4 Steiner Tree Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.5 Vertex Cover Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.6 Practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5 Session 5: Clustering, Facility Location and Scheduling 20
5.1 Clustering and the k-Means Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.2 Uncapacitated Facility Location Problem (UFLP) . . . . . . . . . . . . . . . . . . . . . . . 21
5.3 Parallel Machine Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.4 Practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
,6 Session 6: Traveling Salesperson Problem 26
6.1 Introduction to the TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6.2 Subtour Elimination Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
6.3 Construction Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
6.4 Local Search for TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
6.5 The Symmetric TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
6.6 Real-World TSP: Amazon Last Mile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
7 Session 7: Vehicle Routing Problems 30
7.1 Multiple Traveling Salesperson Problem (MTSP) . . . . . . . . . . . . . . . . . . . . . . . 30
7.2 Alternative: The Route-Based Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . 30
7.3 The Vehicle Routing Problem (VRP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
7.4 Vehicle Routing Problem with Time Windows (VRPTW) . . . . . . . . . . . . . . . . . . 32
7.5 Practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
8 Session 8: Metaheuristics 33
8.1 Introduction: Escaping Local Optima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
8.2 Iterated Local Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
8.3 Variable Neighborhood Search (VNS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
8.4 Accept Non-Improving Neighbours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
8.4.1 TabuSearch (TS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
8.4.2 Simulated Annealing (SA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
8.5 Genetic Algorithms (GA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
8.5.1 The GA Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Definitions Theorems Example: Exercise:
Formulations Bounds and gua- Slide scenarios Conceptual
and core con- rantees. and proofs. questions.
cepts.
Applications of Operation Research
Michael Jackson 2/38
,1 0-1 Knapsack Problems
1.1 Introduction to the 0-1 Knapsack Problem
The 0-1 knapsack problem involves selecting a subset of n items to maximize utility without exceeding a
weight capacity b. Each item i has a weight ai and a utility ci .
Mathematical Formulation
The problem is modeled using binary decision variables xi → {0, 1}, where xi = 1 if item i is
chosen, and 0 otherwise.
n
!
max ci xi
i=1
!n
s.t. ai xi ↑ b
i=1
xi → {0, 1} i = 1, . . . , n
"
Assumptions: n, b, ai , ci are positive integers, ai ↑ b, and ai > b.
Example: The Graduation Gift Budget
You receive €10K. You must choose between indivisible alternatives (exotic trip, car, motorcycle,
etc.) to maximize happiness.
• Variables: x1 (Trip, cost: 4K, util: 4), x2 (Car, cost: 8K, util: 5), x3 (Motorcycle, cost:
3K, util: 4), x4 (Language, cost: 1K, util: 3), x5 (Party, cost: 1K, util: 2), x6 (Redecorate,
cost: 2K, util: 3).
• Constraint: 4x1 + 8x2 + 3x3 + 1x4 + 1x5 + 2x6 ↑ 10
1.2 Complexity and Exact Methods
The 0-1 knapsack problem is NP-hard. While exact methods like branch and bound or dynamic program-
ming can solve it, they are not e!cient in the worst case. Branch and bound may evaluate 2n solutions,
and dynamic programming solves nb subproblems.
1.3 Linear Programming (LP) Relaxation
If items are perfectly divisible, the problem becomes a linear program (LP). We replace the binary
constraint xi → {0, 1} with 0 ↑ xi ↑ 1.
Solution Method: Sort items in decreasing order of their e!ciency ratio acii . Fill the knapsack until
capacity is reached. The first item that does not fully fit is the critical item s, defined as s "
= min{j :
"j b→
s→1
ai
i=1 ai > b}. The optimal LP solution assigns xi = 1 for i < s, xi = 0 for i > s, and xs = i=1
as .
Example: LP Relaxation of the Graduation Gift
Sorting by ratio acii favors the Language (3/1), Party (2/1), Redecorate (3/2), and Motorcycle
(4/3). Taking these uses 7K of the 10K budget. The next best item is the Trip (4K). Because
it’s an LP relaxation, we can take a fraction of it: 10→7
4 = 3/4. The optimal LP solution is
(3/4, 0, 1, 1, 1, 1) yielding a utility of 15.
Applications of Operation Research
Michael Jackson 3/38
,1.4 Relaxations and Dual Bounds
To evaluate heuristics, we compare their solutions to bounds. A Primal Bound is a lower bound (for
maximization) obtained from any feasible solution. A Dual Bound is an upper bound obtained by
solving a relaxation (like the LP yielding 15 in the example above).
↓ Many optimization algorithms compute lower and upper bounds on the optimal value until the
di"erence, called the gap, is small enough.
Formal Definition of a Relaxation
Let original problem P be z P = maxx↑X f (x) and problem R be z R = maxx↑Y g(x). R is a
relaxation of P if:
1. X ↔ Y (the feasible region is expanded).
2. f (x) ↑ g(x) for all x → X (the objective is overestimated).
This guarantees that z P ↑ z R , meaning R provides a valid upper bound.
Objective Value
zR
zP
g(x)
f (x)
x
x↓
Expanded Feasible Region Y
Original Feasible Region X
Figuur 1: Relaxations like defined above
1.5 Heuristics and Performance Guarantees
When exact methods are too slow, we use heuristics to find good feasible solutions quickly.
1.5.1 Rounding Heuristic
Solve the LP relaxation and round down the fractional variable to 0.
Example: Worst-Case Rounding
Setup: Item 1 (c1 = 2, a1 = 1). Item 2 (c2 = 10, a2 = 10). Capacity b = 10.
• LP Solution: Item 1 is more e!cient (2/1 > 10/10). We take all of Item 1, leaving 9
capacity. We take 9/10 of Item 2.
• Rounding: Rounding down the fractional 9/10 leaves us with only Item 1 (utility 2).
• Optimal: Taking Item 2 (utility 10).
Applications of Operation Research
Michael Jackson 4/38
, If Item 2 had utility and weight of 106 , the rounding heuristic still gets 2, while optimal gets 106 .
The performance can be arbitrarily bad.
1.5.2 Greedy Heuristic
Sort items in non-increasing order of their utilities (ci ) and fill the knapsack. If an item doesn’t fit, skip
to the next.
Example: Worst-Case Greedy
Setup: We have n items. Item 1 has c1 = 2, a1 = n ↗ 1. Items 2 to n have ci = 1, ai = 1.
Capacity b = n ↗ 1.
• Greedy Solution: Item 1 has the highest utility (2), so greedy picks it. The knapsack is
now full. Total utility: 2.
• Optimal: Ignore Item 1 and pack all other items (2 to n). Total utility: n ↗ 1.
As n grows, the greedy heuristic remains stuck at 2, performing arbitrarily poorly.
1.5.3 Greedy 2.0
To overcome the arbitrary badness of the previous heuristics, Greedy 2.0 returns the best solution between
the Rounding heuristic (z R ) and the Greedy heuristic (z G ).
z G2 = max{z R , z G }
Performance Guarantee of 2
Greedy 2.0 has a performance guarantee of 2, meaning the optimal value z OP T is never more than
twice the heuristic value z G2 (z OP T ↑ 2z G2 ). Proof Sketch:
"n
1. z OP T ↑ z LP ↑ i=1 ci ↘xLPi ≃.
2. Since the LP solution has at"most one fractional variable, rounding it up adds at most the
maximum utility c↓ . Thus, i ≃↑z +c .
ci ↘xLP R ↓
3. We know c↓ ↑ z G (since the greedy heuristic checks the max utility item).
4. Therefore, z R + c↓ ↑ 2 max{z G , z R } = 2z G2 .
1.6 Practice
Exercise: 0-1 Knapsack Cover Problem
Problem Statement:
n
!
min ci xi
i=1
!n
s.t. ai xi ⇐ b
i=1
xi → {0, 1} i = 1, . . . , n
Questions for consideration:
• Notice the di"erence with the standard 0-1 knapsack problem.
• When does one need to solve a 0-1 knapsack cover problem?
Applications of Operation Research
Michael Jackson 5/38
, • How would you solve the LP relaxation? Can you propose a rounding heuristic and/or a
greedy heuristic?
2 Session 2: Other Knapsack Problems
2.1 0-1 Knapsack Cover Problem
Unlike the standard knapsack problem where we maximize utility under a capacity constraint, the knap-
sack cover problem aims to minimize cost while meeting or exceeding a certain demand constraint.
Example: Choice of Production Plants
Scenario: A company has n production plants and a known demand b. Plant i produces ai units
at a fixed cost ci . The goal is to choose which plants to run to satisfy demand at minimum cost.
n
!
min ci xi
i=1
!n
s.t. ai xi ⇐ b
i=1
xi → {0, 1} i = 1, . . . , n
2.1.1 Lagrangian Relaxation
Instead of dropping the tricky constraint entirely, we can move it to the objective function and penalize
its violation using a Lagrange multiplier ω ⇐ 0.
Lagrangian Relaxation
Let ω ⇐ 0 be the multiplier for the knapsack cover constraint. We define the relaxed problem as:
n
# n
$
! !
z(ω) = min ci xi + ω b ↗ ai xi s.t. xi → {0, 1}
i=1 i=1
Rewriting this makes it easily solvable by inspection:
n
!
z(ω) = ωb + min (ci ↗ ωai )xi
i=1
For each i, if ci ↗ ωai ↑ 0, we set xi = 1; otherwise, xi = 0. Thus:
n
!
z(ω) = ωb + min{ci ↗ ωai , 0}
i=1
The Lagrangian Dual Bound
To find the best lower bound provided by this relaxation, we solve the Lagrangian Dual problem:
z LD = max z(ω)
ω↔0
The Lagrangian dual bound cannot be worse than the LP bound. For this specific relaxation of
the 0-1 knapsack cover problem, z LD gives the exact same bound as the LP relaxation.
Applications of Operation Research
Michael Jackson 6/38
, Example: Evaluating the Bound
Setup: min 5x1 + 4x2 + 2x3 s.t. 2x1 + 3x2 + x3 ⇐ 5; x1 , x2 , x3 → {0, 1}
• LP Optimum: x1 = 1/2, x2 = 1, x3 = 1. Optimal LP value is 8.5. (IP optimal is 9).
• Lagrangian Function: z(ω) = 5ω + min{5 ↗ 2ω, 0} + min{4 ↗ 3ω, 0} + min{2 ↗ ω, 0}
Evaluating z(ω) across its breakpoints (4/3, 2, 5/2) gives a piecewise function. The maximum
value of this function occurs at ω → [4/3, 5/2] yielding z LD = max{20/3, 8, 8.5, 8.5} = 8.5. This
confirms it equals the LP bound!
2.2 0-1 Multiple Knapsack Problem
Here, we have m knapsacks (m < n) with di"erent capacities bj . Each item i can go into at most one
knapsack. We assume each item fits into every knapsack individually, but all items together exceed the
capacity of any single knapsack.
Example: Allocating Orders to Workers
Scenario: You manage m workers to fulfill n orders. Worker j can work for bj time units. Order
i takes ai time and brings ci profit.
!!
max ci xij
i↑N j↑M
!
s.t. xij ↑ 1 ⇒i → N (Each order done by at most 1 worker)
j↑M
!
ai xij ↑ bj ⇒j → M (Worker capacity constraint)
i↑N
xij → {0, 1}
2.2.1 Surrogate Relaxation
Surrogate Relaxation
Given positive multipliers ε1 , . . . , εm , we combine the m capacity constraints into a single cons-
traint: ! ! !
εj ai xij ↑ εj b j
j↑M i↑N j↑M
This creates a single knapsack constraint, providing an upper bound. If all εj are equal, it reduces
directly to a standard 0-1 knapsack problem. "Di"erent choices for εj yield di"erent upper bounds.
When all the εi are equal, and defining yi = j↑M xij , the relaxed problem is the same as
!
max ci yi
i↑N
! !
s.t. ai yi ↑ bj
i↑N j↑M
yi → {0, 1}; i→N
which is a 0-1 knapsack problem
Applications of Operation Research
Michael Jackson 7/38
,2.2.2 Greedy Heuristics for Multiple Knapsacks
Greedy Heuristic: Sort items by ci /ai ⇐ · · · ⇐ cn /an . Fill knapsack 1 until full, then move to knapsack
2, etc. The first item that does not fit in knapsack j is its critical item sj .
Performance Guarantee of Greedy 2.0
Let z G be the value from the standard greedy heuristic. Let csj be the utility of the critical item
for each knapsack j. Define Greedy 2.0’s value as:
!
z G2 = max z G , csj
j↑M
"
Because z G + csj is an upper bound on the LP relaxation of the surrogate relaxation, it also
bounds z OP T . Therefore: !
2z G2 ⇐ z G + csj ⇐ z OP T
j↑M
This guarantees Greedy 2.0 will always yield at least half the optimal value.
2.3 Practice
Exercise: 2-Dimensional Knapsack Problem
You have a bag limited by weight (b1 = 8) and volume (b2 = 10). Each object i has a value ci ,
weight a1i , and volume a2i .
max 4x1 + 3x2 + x3 + 6x4 + 5x5
s.t. x1 + 3x2 + 4x3 + 3x4 + 2x5 ↑ 8 (Weight)
8x1 + x2 + 9x3 + x5 ↑ 10 (Volume)
x1 , x2 , x3 , x4 , x5 → {0, 1}
1. Give a heuristic algorithm for this problem.
2. Propose an instance where your heuristic fails.
3. Apply your heuristic to this specific instance and evaluate the solution quality.
Solution:
1. Heuristic Design: For multidimensional knapsack problems, a greedy heuristic can be
constructed by sorting items according to a resource-weighted e!ciency ratio. Let the ratio
for item i be:
c
Ratioi = + i ,
max b1 , b2
a1i a2i
This penalizes items that consume a large fraction of your strictest bottleneck resource.
2. Failure Concept: Heuristics fail when they greedily lock in items that look highly e!cient
individually but consume resources in a way that blocks a superior combination of multiple
slightly lower-ranked items.
3. Application to Instance: Let’s calculate the bottleneck consumption ratio for each item:
• Item 1: max(1/8, 8/10) = 0.80 =⇑ Ratio1 = 4/0.8 = 5.0
• Item 2: max(3/8, 1/10) = 0.375 =⇑ Ratio2 = 3/0.375 = 8.0
Applications of Operation Research
Michael Jackson 8/38
, • Item 3: max(4/8, 9/10) = 0.90 =⇑ Ratio3 = 1/0.9 ⇓ 1.11
• Item 4: max(3/8, 0/10) = 0.375 =⇑ Ratio4 = 6/0.375 = 16.0
• Item 5: max(2/8, 1/10) = 0.25 =⇑ Ratio5 = 5/0.25 = 20.0
Sorting items by decreasing e!ciency yields the order: Item 5, Item 4, Item 2, Item 1,
Item 3.
Greedy Packing Strategy:
• Pack Item 5: Remaining Weight = 8 ↗ 2 = 6, Volume = 10 ↗ 1 = 9. Profit = 5.
• Pack Item 4: Remaining Weight = 6 ↗ 3 = 3, Volume = 9 ↗ 0 = 9. Profit = 5 + 6 = 11.
• Pack Item 2: Remaining Weight = 3↗3 = 0, Volume = 9↗1 = 8. Profit = 11+3 = 14.
• Item 1 and Item 3 no longer fit due to the weight capacity being completely exhausted.
Heuristic Solution: xHEU R = (0, 1, 0, 1, 1) with an objective value of 14.
Evaluation of Quality: The heuristic solution is sub-optimal. If we bypass Item 2 and
select Item 1 instead, we can construct the feasible bundle {1, 4, 5}. Total Weight = 1 +
3 + 2 = 6 ↑ 8. Total Volume = 8 + 0 + 1 = 9 ↑ 10. Optimal Solution: xOP T = (1, 0, 0, 1, 1)
with an objective value of 15.
Volume (a2 )
Capacity Bounds (8, 10)
I3 (1)
I1 (4) Optimal
Bundle
(I1+I4+I5)
= 15
Heuristic
Bundle
(I2+I4+I5)
= 14
I2 (3)
I5(5)I4 (6)
Weight (a1 )
Exercise: 1-Dimensional Cutting Stock Problem
Materials are supplied in master pieces of standard length L. There is a demand di for smaller
pieces of length li ↑ L. Goal: minimize the total number of master pieces needed to satisfy
demand.
1. Model the problem mathematically.
2. Develop a construction heuristic.
3. Give an explicit counterexample instance where the heuristic fails.
Applications of Operation Research
Michael Jackson 9/38
, 4. Find a heuristic with a performance guarantee of 2 using a waste argument.
Solution:
1. Mathematical Model (Kantorovich Formulation): Let " W be a conservative upper
bound on the number of master pieces needed (e.g., W = di ). Define binary variables
yj = 1 if master piece j is used, 0 otherwise. Define integer variables xij ⇐ 0 as the number
of times item i is cut from master piece j.
W
!
min yj
j=1
W
!
s.t. xij ⇐ di ⇒i = 1, . . . , n (Demand fulfillment)
j=1
!n
li xij ↑ Lyj ⇒j = 1, . . . , W (Length capacity constraint)
i=1
yj → {0, 1}, xij ⇐ 0 and integer
2. Construction Heuristic: First-Fit Decreasing (FFD). Sort all demanded items in
non-increasing order of their lengths. Iterate through the sorted items and place each one
into the first already-opened master piece that has enough remaining residual capacity. If it
fits nowhere, open a new master piece.
3. Counterexample Instance: Let master piece length L = 10. Suppose the total demand
consists of: two pieces of length 4 and four pieces of length 3.
Running the FFD heuristic (Sorted items: 4, 4, 3, 3, 3, 3):
• Bar 1: Packs the two 4s. Remaining capacity = 10 ↗ 4 ↗ 4 = 2. None of the remaining
pieces of length 3 can fit.
• Bar 2: Packs three 3s. Remaining capacity = 10 ↗ 3 ↗ 3 ↗ 3 = 1.
• Bar 3: Packs the final remaining piece of length 3.
FFD uses 3 bars. However, the optimal arrangement splits the pairs:
• Bar 1: One 4, two 3s (Total = 4 + 3 + 3 = 10). Remaining capacity = 0.
• Bar 2: One 4, two 3s (Total = 4 + 3 + 3 = 10). Remaining capacity = 0.
The true optimal solution requires only 2 bars. FFD fails.
4. Performance Guarantee of 2 (Next-Fit Waste Proof): Consider the simple Next-Fit
(NF) heuristic. NF packs items into the current master piece; when an item doesn’t fit, it
permanently closes that master piece and opens a new one.
Let M be the total number of bars used by Next-Fit. Consider any two consecutive bars j
and j + 1. Let Wj be the used capacity in bar j and Wj+1 the used capacity in bar j + 1.
Because the first item in bar j + 1 failed to fit into bar j, it must be true that:
Wj + (first item length in bar j + 1) > L =⇑ Wj + Wj+1 > L
Summing this inequality across all consecutive pairs of bars implies that the total combined
content of the occupied bars satisfies:
M ↗1
n
!
d i li > L
i=1
2
Applications of Operation Research
Michael Jackson 10/38
