Applications of Operations Research
Lecture 1
NP-hard
= nobody could come up with an efficient algorithm to solve this problem
0/1 Knapsack Problem
- NP-hard
- Solve by using branch-and-bound or by dynamic programming (both not efficient in worst
case)
- Rounding heuristic (solve LP relaxation and round)
- Greedy algorithm (don’t look ahead, but just look at the immediate benefit of your action)
- Greedy 2.0 = max{rounding, greedy} – performance guarantee of 2
Assignment Problem
- Polynomial
- Algorithm: can be solved as a LP (gives integer optimal solution – matrix is unimodular)
Shortest Path Problem
- NP-hard (IF there are negative length directed cycles ELSE polynomial)
- If no lengths < 0: Dijkstra (polynomial)
- If some lengths <0, but no negative cycles: Bellman-Ford (polynomial)
- Solving LP always yields optimal integer solution (matrix is unimodular)
Minimum Spanning Tree (MST) problem
- Polynomial
- Tree = connected subgraph that does not contain cycles, it is spanning if it contains all the
vertices of the graph
- Two models:
o With connectivity constraints (sum of weights of edges larger than 1)
o With subtour elimination constraints (sum of weights of edges smaller than S-1)
o Feasible set of LP relaxation of model 2 is the subset of the feasible set of LP
relaxation of model 1. Hence, model 2 is a stronger model than model 1.
- Kruskal’s algorithm (exact algorithm = computes optimal solution) – it’s a greedy algorithm
, Lecture 2
Vertex Cover Problem
- NP-hard
- Rounding heuristic (easy for this problem) – always a feasible solution
- Correctness (proof by contradiction – slide 7)
- Performance guarantee of 2 (slide 8)
- Greedy heuristic (minimize ratio of weight/degree)
(Data) Clustering Problem
- NP-hard
- K-means algorithm (heuristic algorithm)
o Choose K random cluster centers (initialization)
o Assign observations to closest center
o Calculate new center if assignments did change (else stop)
Uncapacitated Facility Location (UFL) Problem
- NP-hard
- Greedy heuristic (look at net savings)
- Construction heuristic = builds a feasible solution from scratch
- Improvement heuristic = takes a feasible solution as input and tries to find a better one
- Local search (= improvement heuristic)
o Tricky to define neighborhood (=key step)
o Trade off = time spent vs. quality of the solution
Parallel Machine Scheduling Problem
- NP-hard
- Local search (define neighborhood!)
o Performance guarantee of 2 (slide 53)
- Greedy algorithm = list scheduling algorithm
o Performance guarantee of 2 (slide 54) – because local search does not improve the
greedy algorithm anymore
Lecture 1
NP-hard
= nobody could come up with an efficient algorithm to solve this problem
0/1 Knapsack Problem
- NP-hard
- Solve by using branch-and-bound or by dynamic programming (both not efficient in worst
case)
- Rounding heuristic (solve LP relaxation and round)
- Greedy algorithm (don’t look ahead, but just look at the immediate benefit of your action)
- Greedy 2.0 = max{rounding, greedy} – performance guarantee of 2
Assignment Problem
- Polynomial
- Algorithm: can be solved as a LP (gives integer optimal solution – matrix is unimodular)
Shortest Path Problem
- NP-hard (IF there are negative length directed cycles ELSE polynomial)
- If no lengths < 0: Dijkstra (polynomial)
- If some lengths <0, but no negative cycles: Bellman-Ford (polynomial)
- Solving LP always yields optimal integer solution (matrix is unimodular)
Minimum Spanning Tree (MST) problem
- Polynomial
- Tree = connected subgraph that does not contain cycles, it is spanning if it contains all the
vertices of the graph
- Two models:
o With connectivity constraints (sum of weights of edges larger than 1)
o With subtour elimination constraints (sum of weights of edges smaller than S-1)
o Feasible set of LP relaxation of model 2 is the subset of the feasible set of LP
relaxation of model 1. Hence, model 2 is a stronger model than model 1.
- Kruskal’s algorithm (exact algorithm = computes optimal solution) – it’s a greedy algorithm
, Lecture 2
Vertex Cover Problem
- NP-hard
- Rounding heuristic (easy for this problem) – always a feasible solution
- Correctness (proof by contradiction – slide 7)
- Performance guarantee of 2 (slide 8)
- Greedy heuristic (minimize ratio of weight/degree)
(Data) Clustering Problem
- NP-hard
- K-means algorithm (heuristic algorithm)
o Choose K random cluster centers (initialization)
o Assign observations to closest center
o Calculate new center if assignments did change (else stop)
Uncapacitated Facility Location (UFL) Problem
- NP-hard
- Greedy heuristic (look at net savings)
- Construction heuristic = builds a feasible solution from scratch
- Improvement heuristic = takes a feasible solution as input and tries to find a better one
- Local search (= improvement heuristic)
o Tricky to define neighborhood (=key step)
o Trade off = time spent vs. quality of the solution
Parallel Machine Scheduling Problem
- NP-hard
- Local search (define neighborhood!)
o Performance guarantee of 2 (slide 53)
- Greedy algorithm = list scheduling algorithm
o Performance guarantee of 2 (slide 54) – because local search does not improve the
greedy algorithm anymore
