| Course Outline | General Information | Study Material | Lectures (classwise) | Assignment |
The course consists of 2 double lectures per week.
The basic thrust of the course would be to study optimization techniques from computer science perspective.
The basic course outline is given in this page.
We would assume in this course that you have undergone the Data and File Structures, Design and Analysis of Algorithms and Discrete Mathematics courses and have some knowledge of elementary discrete probability and linear algebra.
| Class Timings: | Tuesday 09:30-11:10, Thursday 09:30-11:10 Room No. xxx-xxx, S. N. Bose Bhavan (Library Building) |
| The necessary evil - marks, exam, etc.: | Mid-sem: 30, End-sem: 50, Internal evaluation: 20 |
| Books |
(B1) Understanding and Using Linear Programming Jiří Matoušek and Bernd Gärtner Springer (B2) Linear Programming -- Foundations and Extensions Robert J. Vanderbei Springer (B3) Combinatorial Optimization -- Algorithms and Complexity Christos H. Papadimitriou and Kenneth Steiglitz Dover Publications (B4) Linear and Non-linear Programming David G. Luenberger and Yinyu Ye Springer (B5) Linear Programming Vašek Chvátal W. H. Freeman & Co. Ltd. (B6) Linear Algebra Jin Ho Kwak & Sungpyo Hong Birkhäuser (B7) Approximation Algorithms Vijay V. Vazirani Springer (B8) The Design of Approximation Algorithms David P. Williamson and David B. Shmoys Cambridge (B9) Computational Geometry: Algorithms and Applications Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars Springer Verlag |
| Web Resources |
(W1) MIT OCW on Optimization Methods (W2) Lecture Notes (by Sanjeev Arora) (W3) Lecture Notes (by Santosh Vempala) (W4) Lecture Notes (by Michael Goemans) (W5) An Introduction to the Conjugate Gradient Method Without the Agonizing Pain (by Jonathan R. Shewchuk) |
| LECTURE DATES | TOPICS | NOTES (pdf) | BOOKS |
| Lecture 1 (18-07-2017) |
Introduction to Mathematical Program: LP, ILP, Non-linear Program, etc. Writing different problems as mathematical program | - | (B1), (B2), (B3), (W1) |
| Lecture 2 (20-07-2017) |
Introduction to Linear Program: Geometric interpretation, feasible region, types of solutions: infeasible and feasible, bounded and unbounded, unique and infinitely many solutions | - | (B1), (B2), (B3), (W1) |
| Lecture 3 (25-07-2017) |
Linear Programming in low dimensions: use of geometry Randomized incremental algorithm for LP in low dimensions | - | (B9) |
| Lecture 4 (27-07-2017) |
Maximum weight bipartite matching as an ILP Minimum Vertex Cover: ILP and a 2-factor approximation by LP relaxation; Maximum independent set | - | (B1) |
| Lecture 5 (01-08-2017) |
Fitting a line; handling mod functions; handling logical conditions Basic Feasible Solution; | - | (B1) |
| Lecture 6 (03-08-2017) |
SIMPLEX | - | (B1) |
| Lecture 7 (10-08-2017) |
SIMPLEX | - | (B1), (B4), (B5) |
| Lecture 8 (17-08-2017) |
Cycling in SIMPLEX; Pivot Rules | - | (B1), (B5) |
| Lecture 9 (22-08-2017) |
Duality | - | (B1) |
| Lecture 10 (24-08-2017) |
Some basics in Linear Algebra | - | (B1), (B6) |
| Lecture 11 (29-08-2017) |
Basic Feasible Solution and Linear independence; Fundamental Theorem of LP; | - | (B4), (B1) |
| Lecture 12 (31-08-2017) |
Fundamental Theorem of LP: the relation between optimal feasible solution and optimal BFS and optimal BFS and extremum points of the feasible convex polyhedron | - | (B4), (B1) |
| Lecture 13 (19-09-2017) |
Max-flow Min-cut theorem (in the light of primal dual) | - | (B7) |
| Lecture 14 (21-09-2017) |
Matchings and Vertex Covers in bipartite graphs (in the light of primal dual) -- Hall's theorem and König's theorem; Totally unimodular matrices |
- | (B1) |
| Lecture 15 (12-10-2017) |
Matching and vertex cover in bipartite graph (contd.) | - | (B1) |
| Lecture 16 (17-10-2017) |
Two Player Zero sum games (in the light of primal dual), Existence and computation of mixed Nash equilibrium, Minimax theorem for zero-sum games |
- | (B1) |
| Lecture 17 (24-10-2017) |
Farkas Lemma | - | (B1) |
| Lecture 18 (26-10-2017) |
Farkas Lemma and strong duality theorem | - | (B1) |
| Lecture 19 (31-10-2017) |
Interior point methods for solving LP | - | (B1) |
| Lecture 20 (02-11-2017) |
Interior point method for solving LP | - | (B1) |
| Lecture 21 (07-11-2017) |
Ellipsoid method for solving LP | - | (B1), (W2,W3,W4) |
| Lecture 22 (09-11-2017) |
Lagrangian multipliers for solving constrained nonlinear programs |
- | (B4) |