CS508 - Optimization Methods

About     |     General Information     |     Study Material     |     Lectures (classwise)     |     Assignments

About

This course is intended to the students who want to understand the rich theoretical and engineering aspects of various optimization techniques such as linear programming (LP), integer linear programming (ILP), and decision procedures such as Boolean satisfiability (SAT), and satisfiability modulo theory (SMT) that are widely used in CAD algorithms, testing, security, and computer-aided verification.

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
Solution
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
01
Feb 24, 2020
Problem statement     |     Submission instructions