Algorithmic Operations Research

Models and applications. NP-hard problems. Linear programming: the simplex method and duality theory. The transportation problem, matching and assignment problems. Total unimodular problems. Integer programming and relaxation. Branch and bound techniques: the 0-1 knapsack problem, covering and packing problems. Dynamic programming technique, heuristics, local search – PLS completeness and simulated annealing. Applications: maximum independent set problem, vertex cover, max cut, quadratic assignment problem, data placement, facility location, cutting stock problems.