| 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. 709-710, 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 |
| 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 (02-08-2016) |
Introduction to Linear Program: Geometric interpretation, feasible region, types of solutions: infeasible and feasible, bounded and unbounded, unique and infinitely many solutions Recapitulation of NP-complete problems. | - | (B1), (B2), (B3), (W1) |
| Lecture 2 (04-08-2016) |
Recapitulation of NP-completeness; Integer Program(IP) – introduction; ILP ILP is NP-complete; Approximation algorithms |
- | (B7), (B8) |
| Lecture 3 (09-08-16) |
Minimum Vertex Cover: ILP and a 2-factor approximation by LP relaxation; Maximum independent set; Minimum Set Cover: ILP and a f-factor approximation by LP relaxation; |
- | (B1), (B8) |
| Lecture 4 (11-08-16) |
Formulating different problems (network flow, line fitting, sorting, shortest path, minimum spanning tree, graph coloring) as optimization problem; Standard form of an LP; |
- | (B1) |
| Lecture 5 (16-08-16) |
Minimum Weight Bipartite Matching | - | (B1) |
| Lecture 6 (18-08-16) |
Introduction to Linear Algebra -- I | - | (B6) |
| Lecture 7 (23-08-16) |
Introduction to Linear Algebra -- II | - | (B6) |
| Lecture 8 (25-08-16) |
Introduction to Linear Algebra -- III | - | (B6) |
| Lecture 9 (29-08-16) |
Linear Algebra -- IV; Basic feasible solution of an LP and its relation to linear independence; |
- | (B1) |
| Lecture 10 (30-08-16) |
Simplex | - | (B1) |
| Lecture 11 (01-09-16) |
Simplex and BFS, Bland's rule, Initial BFS, Idea of auxiliary LP | - | (B1), (B4) |
| Lecture 12 (06-09-16) |
Basic feasible solution of an LP and its relation to linear independence; Fundamental Theorem of LP |
- | (B1), (B4) |
| Lecture 13 (08-09-16) |
Basic feasible solution, linear independence and extreme points of the convex polytope; |
- | (B1), (B4) |
| Lecture 14 (15-09-16) |
Duality of Linear Program; Weak and Strong duality theorem |
- | (B1), (B4) |
| Lecture 15 (27-09-16) |
Matchings and Vertex Covers in bipartite graphs -- Hall's theorem and Konig's theorem; Totally unimodular matrices |
- | (B1) |
| Lecture 16 (29-09-16) |
Relaxed ILPs and integral solutions of LP; Maximum matching and minimum vertex cover in bipartite graphs |
- | (B1) |
| Lecture 17 (04-10-16) |
Network flow and its LP formulation, Primal (and dual) complementary slackness condition |
- | (B1) |
| Lecture 18 (06-10-16) |
Slackness conditions; Set Cover |
- | (B1), (B8) |
| Lecture 19 (18-10-16) |
Zero-Sum Games; Existence and computation of a mixed Nash equilibrium | - | (B1) |
| Lecture 20 (20-10-16) |
Minimax theorem for zero-sum games | - | (B1) |
| Lecture 21 (25-10-16) |
Farkas lemma -- geometric and linear algebraic interpretations; Separating hyperplane theorem |
- | (B1) |
| Lecture 22 (27-10-16) |
Duality using Farkas lemma | - | (B1) |
| Lecture 23 (03-11-16) |
Upper bounds on solutions of LP | - | (B3) |
| Lecture 24 (07-11-16) |
Ellipsoid method for LP -- I | - | (B1), (W2, W3, W4) |
| Lecture 25 (08-11-16) |
Ellipsoid method for LP -- II | - | (B1), (W2, W3, W4) |
| Lecture 26 (10-11-16) |
Ellipsoid method for LP -- III | - | (B1), (W2, W3, W4) |
| Lecture 27 (15-11-16) |
Nonlinear Programming -- I | - | (W5) |
| Lecture 28 (17-11-16) |
Nonlinear Programming -- II: Steepest Descent | - | (W5) |
| Lecture 29 (18-11-16) |
Nonlinear Programming -- III: Conjugate Direction | - | (W5) |
| Lecture 30 (22-11-16) |
Nonlinear Programming -- IV: Conjugate Gradient | - | (W5) |
| Lecture 31 (23-11-16) |
Lagrange multiplier; Interior Point Method for LP -- I |
- | (B1), (B4) |
| Lecture 32 (24-11-16) |
Interior Point Method for LP -- II | - | (B1), (B4) |