Discrete optimization problems form the basis of solutions to problems in several areas of computer science, operations research and economics. The work-horse of discrete optimization is integer and linear programming. The course will introduce the theory of linear programs, as well as algorithms for solving them. We will then look at fundamental discrete optimization problems, study LP based techniques, as well as specialized combinatorial algorithms for solving these problems. We will also briefly cover integer programming and techniques to solve them. Students may be required to write a survey paper, or do a research project.
Learn to model discrete optimization problems using Integer/Linear programs.
Learn about the geometry of linear programs, and the concept of duality.
Learn about algorithms to solve IP/LP.
Learn about the state-of-the-art in fundamental combinatorial optimization problems such as cuts, flows, matchings, MST, matroids, TSP, Steiner trees, etc.