CS508 - Optimization Methods

General Information


Class Schedule

Monday (11:00am-11:55am)
Tuesday (11:00am-11:55am)
Friday (10:00am - 10:55am)

Venue

1201

TAs

Partha Sarathi Pati
partha.pati AT iitg.ac.in
Shrestha Tripathy
shrestha AT iitg.ac.in
Harsh Meheta
harsh18a AT iitg.ac.in

Grade Calculation

Quizzes: 10 %
Assignments: 30 %
Mid-sem: 30 %
End-sem: 30 %

Study Materials

  • B1 - Understanding and Using Linear Programming, Jiří Matoušek and Bernd Gärtner, Springer
  • B2 - Combinatorial Optimization -- Algorithms and Complexity, Christos H. Papadimitriou and Kenneth Steiglitz, Dover Publications
  • B3 - The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys, Cambridge
  • B4 - Approximation Algorithms, Vijay V. Vazirani, Springer
  • B5 - Linear and Non-linear Programming, David G. Luenberger and Yinyu Ye, Springer
  • W1 - Linear Algebra -- Prof. Gilbert Strang
  • B6 - Decision Procedures: An Algorithmic Point of View, Daniel Kroening, Ofer Strichman, Springer
  • B7 - Handbook of Satisfiability, Editors: Armin Biere, Marijn Heule, Hans van Maaren, Toby walsh, IOS Press

Lectures (classwise)

#
Date
Topics
Readings
01
Jan 3, 2020
Introduction to Optimization Problems
Introduction to LP: Geometric interpretation, feasible region, types of solutions: infeasible and feasible, bounded and unbounded, unique and infinitely many solutions
B1, B2
02
Jan 6, 2020
Writing different problems as mathematical program: vertex cover, set cover, graph coloring; Handling mod function: production planning, line fitting
B1, B3
03
Jan 7, 2020
Maximum weight bipartite matching as ILP, Optimal solution with LP relaxation
B1
04
Jan 10, 2020
Minimum Vertex Cover: ILP and a 2-factor approximation by LP relaxation; Maximum independent set; Set cover
B1, B3
05
Jan 13, 2020
Basics of linear algebra; System of linear equations: Ax = b
W1
06
Jan 14, 2020
System of linear equations: Ax = b; Basic feasible solution
W1, B1
07
Jan 20, 2020
Demo: Cplex optimizer
W1, B1
08
Jan 21, 2020
Simplex
B1
09
Jan 24, 2020
Exception Handling in Simplex: Unboundedness, Degeneracy
B1
10
Jan 27, 2020
Exception Handling in Simplex: Infeasibilty; Cycling in Simplex
B1
11
Jan 28, 2020
Pivot Rules, Duality
B1
12
Feb 3, 2020
Fundamental Theorem of LP; Weak duality theorem
B1, B5
13
Feb 4, 2020
Strong Duality Theorem
B1
14
Feb 7, 2020
Complementary Slackness; Approximation of set cover
B3, B4
15
Feb 10, 2020
Primal dual algorithm for the set cover problem
B3
16
Feb 11, 2020
Max-flow Min-cut theorem (in the light of primal dual)
B4
17
Feb 17, 2020
Matchings and Vertex Covers in bipartite graphs (in the light of primal dual) -- Hall's theorem and König's theorem; Totally unimodular matrices
B1
18
Feb 18, 2020
Class Test 1
19
Feb 21, 2020
Tutorial 1
20
Feb 24, 2020
Tutorial 2
21
March 1, 2020
Mid Semestaral Examination
22
Mar 8, 2020
Farkas Lemma
B1
23
Mar 12, 2020
Farkas Lemma and Strong Duality Theorem
B1
24
Mar 13, 2020
Boolean Satisfiabilty: Introduction, Modeling
B6

Assignment(s)

#
Due on
Link