Home Research Teaching Publications index
January 2020
This course will give an introduction to combinatorial optimization. This is an elective course for both undergraduate and postgraduate students.
Algorithms and Linear algebra course.
See notes on LP here.
We expect every student to follow the highest standards of integrity and academic honesty. Copying/sharing code in exams, homeworks, labs are not allowed. See the IIT Goa policy for academic malpractices.
| # | Date | Topic | Resources |
|---|---|---|---|
| 1 | 8/1 | Introduction to combinatorial optimization. Matrix multiplication | |
| 2 | 9/1 | Knapsack problem | Tardos, Prof. Ranade's lecture |
| Bipartite matching problem | Prof. Ranade's lecture | ||
| 3 | 16/1 | Bipartite matching problem continued. | " |
| Introduction to Linear algebra - Vectors, matrices, row view, column view, matrix multiplication, special matrices: square, symmetric, identity. Inverse of a matrix | any linear algebra book | ||
| 4 | 17/1 | Row/Column space, rank, orthogonal vectors, null space, fundamental theorem of linear algebra | any linear algebra book |
| 5 | 21/1 | Linear algebra tutorial - geometry of lines, gaussian elimination, when is Ax=b solvable?, "special" solutions when Ax=b has infinite solutions. | |
| 6 | 23/1 | Introduction to Linear programming - diet problem example, the LP problem, 2-D geometric view and finding min and max | |
| 7 | 24/1 | Different LP problems. Feasible solution, basic feasible solution (bfs) | lecture notes |
| 8 | 30/1 | Existence of basic feasible solution | " |
| Affine set, affine combination of points | " | ||
| 9 | 31/1 | Convex sets - examples, closure properties, Convex Hull of a set | " |
| 10 | 6/2 | Optimal solution is found at a bfs | " |
| convex hull of bfs = feasible solution (for closed bounded sets) | |||
| 11 | 7/2 | Finishing proof of convex hull of bfs = feasible solution | |
| Observering the close relationship between geometric and algebraic view | |||
| Observe through example neighbouring vertices | |||
| 12 | 13/2 | Traversing from one bfs to another bfs | |
| Finding an initial bfs | |||
| 13 | 14/2 | The simplex algorithm | lecture notes |
| Proof of correctness | |||
| 14 | 24/2 | Tutorial | |
| 15 | 25/2 | Bipartite graph problem reduced to LP | lecture notes |
| Bit complexity - How big can the solution to an LP become? | |||
| - | Mid semesester examination | ||
| - | Mid semester break | ||
| COVID break | |||
| 16 | 28/3 | Duality - Primal problem, dual problem, Conversion from primal to dual and back | |
| 17 | 1/4 | Weak duality theorem | |
| Three types of LP - no feasible point, has feasible point but no solution (unbounded), solution exists | |||
| 18 | 2/4 | Farka's lemma - Intuition and proof | |
| 19 | 8/4 | Strong duality theorem | |
| 20 | 9/4 | Tableau method | |
| 21 | 10/4 | Tableau and strong duality | |
| Complementary slackness theorem | |||
| 22 | 16/4 | Review of Duality and complementary slackness theorem | |
| 23 | 17/4 | Relook at Tableau method | |
| 24 | 24/4 | Primal dual algorithm | |
| 25 | 29/4 | Shortest path - Encoding as an LP, how simplex works?, what is the dual of this problem? | |
| 26 | 30/4 | Shortest path problem - Primal dual algorithm | |
| 27 | 4/5 | Shortest path problem - Primal dual algorithm continued | |
| 28 | 5/5 | Geometry of ellipsoid | |
| 29 | 12/5 | Ellipsoid algorithm - polynomial time algorithm for LP | Papadimitriou's book |
| 30 | 19/5 | Ellipsoid algorithm continued | Papadimitriou's book |