Home Research Teaching Publications index

CS 520: Combinatorial optimization

January 2020

This course will give an introduction to combinatorial optimization. This is an elective course for both undergraduate and postgraduate students.

Time and Place


Algorithms and Linear algebra course.

Lecture notes

See notes on LP here.



Syllabus (not necessarily in this order)

Grading Policy (tentative)

Academic Honesty

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.

Course Schedule

# 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