| 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 a CS perspective.
We will try to stick to the basic course outline as given in this page, but may deviate a bit.
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: | Monday 10:00-11:40, Wednesday 10:00-11:40 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 |
| Web Resources | (W1) MIT OCW on Optimization Methods |
| LECTURE DATES | TOPICS | NOTES (pdf) | BOOKS |
| Lecture 1 (03-08-2015) |
Introduction to Optimization Problem; Formulating different problems (network flow, transportation, line fitting, independent set, etc.) as optimization problems; | - | (B1), (B3), (W1) |
| Lecture 2 (05-08-15) |
Linear Program(LP) and its geometric interpretation Notions of infeasible and feasible LP bounded and unbounded LP; unique and infinitely many solutions of an LP; |
- | (B1), (B2), (W1) |
| Lecture 3 (11-08-15) |
Techniques of writing an LP in standard form; Recapitulation of NP-completeness; Integer Program(IP) -- introduction; IP is NP-complete |
- | (B1) |
| Lecture 4 (12-08-15) |
Notions of Integer Linear Program (ILP); Maximum Weight Bipartite Matching |
- | (B1) |
| Lecture 5 (17-08-15) |
Introduction to Approximation algorithms; Minimum Vertex Cover -- ILP formulation and LP relaxation; approximation algorithm. |
- | (B1) |
| Lecture 6 (19-08-15) |
Introduction to Linear Algebra -- I | - | (B6), (B1) |
| Lecture 7 (24-08-15) |
Introduction to Linear Algebra -- II | - | (B6), (B1) |
| Lecture 8 (26-08-15) |
Introduction to Linear Algebra -- III | - | (B6), (B1) |
| Lecture 9 (31-08-15) |
Introduction to Linear Algebra -- IV, Convexity | - | (B6), (B1) |
| Lecture 10 (02-09-15) |
Basic feasible solution of an LP and its relation to linear independence; Fundamental Theorem of LP |
- | (B1), (B4) |
| Lecture 11 and 12 (07-09-15) |
Basic feasible solution, linear independence and extreme points of the convex polytope; Simplex |
- | (B1), (B4) |
| Lecture 13 (10-09-15) |
Simplex and BFS, Bland's rule, Initial BFS, Idea of auxiliary LP | - | (B1), (B4) |
| Lecture 14 (10-09-15) |
P, co-P, NP, co-NP; yes and no certificates; Primal Dual, Duality of LP, weak duality theorem |
- | (B1), (B4), (B7) |
| Lecture 15 (14-09-15) |
Strong duality theorem; consequences of weak and strong duality theorem on (un)boundedness and (in)feasibility of LPs complementary slackness conditions |
- | (B1), (B4) |
| Lecture 16 (16-09-15) |
Totally unimodular matrix, relaxed ILPs and integral solutions of LP |
- | (B1), (B4) |
| Lecture 17 (17-09-15) |
Maximum matching and minimum vertex cover in bipartite graphs Network flows |
- | (B1), (B4) |