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.

- LT3, Thu 9.30-11.00 am
- LT3, Fri 9.30-11.00 am

Algorithms and Linear algebra course.

See notes on LP here.

- Combinatorial optimization by Papadimitriou
- Linear programming by Matousek

- Prof. Sundar Vishwanathan's notes
- Theory of Linear and Integer programming by Schrijver
- Linear programming by Gass
- Approximation algorithm by Vazirani
- Algorithm design by Tardos

- Introduction to combinatorial optimization - Some example problems.
- Linear Programming (LP)
- The problem and its variants
- Reductions to LP - solving other problems by reductions to LP
- Properties of LP
- Algorithms for solving LP
- Simplex
- Polynomial algorithm(s)

- Introduction to Integer programming (if time permits)
- Introduction to Convex optimization (if time permits)

- Midterm (25%) — Final (40%) - Assignments(25%) - Term paper(10%)

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 |