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

Pre-requisite

Algorithms and Linear algebra course.

Books

Reference

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)
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
Proof of correctness
14 24/2 Tutorial
15 25/2 Bipartite graph problem reduced to LP
Bit complexity - How big can the solution to an LP become?

Assignments

# Problem Due date