CS538: COMBINATORIAL OPTIMIZATION SPRING 2023
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
SPRING 2023
CS538: COMBINATORIAL OPTIMIZATION
SB 225,MW 5-6.15
The course will deal with Optimization Algorithms, with special em- phasis on Combinatorial Methods. The topics include classical methods of Linear Programming and Duality and their application to Combinatorial Optimization and Operations Research. Polynomial algorithms for linear programming will be discussed, including the Ellipsoid Method and Interior point method (time permitting). In particular we will consider primal-dual methods in the context of classical graph theoretic problems like maximum flows, matching transshipment problem etc. Specific Topics are listed.
We will also consider related important NP-Hard optimization problems and integer programming. The problems and methods find applications in Network Design and other domains of computer science as well as in areas of Management and Economic sciences.
References for the course:
(i) Course Book: Combinatorial Optimization: Algorithms and Com- plexity by C.H. Papadimitriou and K. Steiglitz (Dover Publications)
(ii) Combinatorial Optimization, Eugene Lawler (Dover)
(iii) Introduction to Algorithms, Corman, T.H., Leiserson, C.E., and Rivest, R.L. (McGraw Hill)
There will be 4-5 homeworks, and (time permitting) a project. Exams will be partly in class and part take-home. HW 35%, Midterm 20%, final 30%, Project 10%. There will be informal home works given in class. Stu- dents are expected to attend/watch the lectures and solve the home works. These will carry a weight of 5%
Specific Topics
Topics:
Lecture 1: Introduction and Modeling
Lecture 2: Duality theorems: Illustration of Weak Duality
Lecture 3: Illustration of weak Duality in LP
Lecture 4: Convex function and Sets
Lecture 5: Condition for convexity, Local-global optimality
Lecture 6: Convex Optimization, Lagrangian Dual function,
Lecture 7: KKT conditions, LP Duality, LP and Polytopes
Lecture 8: Geometry of Linear Programs, Basic Feasible solutions
Lecture 9: Correspondence between Polytopes and BFS
Lecture 10: Moving from BFS to adjacent BFS and Simplex.
Lecture 11: Simplex continued
Lecture 12: Application to Max-Flow problem
Lecture 13: Algorithms for Max-Flow
Lecture 14: Analysis of algorithms for Max-Flow
Lecture 15: Improved algorithms for Maximum Flow
Lecture 16: Improved algorithms for Max-Flow
Lecture 17: Transshipment Problem, Solving via Flows
Lecture 18: Solving via primal-dual method
Lecture 19: Matching algorithms, Bipartite Graphs
Lecture 20: Assignment problems
Lecture 21: General Graph Matching
Lecture 22: Unimodularity and integer solutions
Lecture 23: Ellipsoid Method
Lecture 24: Interior point Methods.
Lecture 25: Interior point Methods.
2023-03-22