Overview of different lectures. Gives insights in different problems and its heuristics. Also proof of optimality and comparison between different modeling structures.
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
Les avantages d'acheter des résumés chez Stuvia:
Qualité garantie par les avis des clients
Les clients de Stuvia ont évalués plus de 700 000 résumés. C'est comme ça que vous savez que vous achetez les meilleurs documents.
L’achat facile et rapide
Vous pouvez payer rapidement avec iDeal, carte de crédit ou Stuvia-crédit pour les résumés. Il n'y a pas d'adhésion nécessaire.
Focus sur l’essentiel
Vos camarades écrivent eux-mêmes les notes d’étude, c’est pourquoi les documents sont toujours fiables et à jour. Cela garantit que vous arrivez rapidement au coeur du matériel.
Foire aux questions
Qu'est-ce que j'obtiens en achetant ce document ?
Vous obtenez un PDF, disponible immédiatement après votre achat. Le document acheté est accessible à tout moment, n'importe où et indéfiniment via votre profil.
Garantie de remboursement : comment ça marche ?
Notre garantie de satisfaction garantit que vous trouverez toujours un document d'étude qui vous convient. Vous remplissez un formulaire et notre équipe du service client s'occupe du reste.
Auprès de qui est-ce que j'achète ce résumé ?
Stuvia est une place de marché. Alors, vous n'achetez donc pas ce document chez nous, mais auprès du vendeur sepm13. Stuvia facilite les paiements au vendeur.
Est-ce que j'aurai un abonnement?
Non, vous n'achetez ce résumé que pour €5,49. Vous n'êtes lié à rien après votre achat.
