Mathematical Programming

Course code	COL756
Instructor	Ashish Chiplunkar
Teaching Assistant	Ajay Soni
Classes	Tuesday, Wednesday, Friday 10:00 - 11:00 (Slot E)
Office hour	TBD

How to contact the instructor

If your issue is relevant to most of the class, post on course's discussion forum on Teams or Piazza. Else, send a personal message to the instructor on Teams. Avoid sending emails to the instructor (they could get lost among spam), but if you must, send one to ashishc@iitd... with the subject line beginning with [COL756].

Prerequisites

Linear algebra: Vector spaces, linear independence, span, basis and dimension, linear transformations, matrices and their inversion
Discrete mathematics: specifically, graph theory
Algorithms: Shortest path, min-weight spanning tree, maxflow-mincut

Content (tentative)

Linear Programming Problems, the Geometry of Feasible Spaces and the set of Optima
The Simplex Algorithm
LP Duality and Complementary Slackness
Application to Combinatorial Problems: Shortest Path, Min-weight Spanning Tree, Maxflow-mincut, Matchings, Min-Cost Flow
The Ellipsoid Algorithm
Semidefinite Programming and Goemans-Williamson Algorithm
Convex Optimization, Lagrangian Dual, algorithms
Extension Complexity

Reference Books

"Combinatorial Optimization" by Christos H. Papadimitriou, Kenneth Steiglitz
"Convex Optimization" by Stephen Boyd, Lieven Vandenberghe; available online

Useful Platforms

Microsoft Teams for live lectures, tutorials, announcements, and exam proctoring
Impartus for recorded lectures (see the 'Flipped Lectures' tab) and notes / slides (see the 'Backpack' tab)
Gradescope for submitting homeworks and exams
Piazza for discussions

Evaluation Policy

Homeworks	20%	To be done in groups of size ≤ 3
Minor exams	40%	2 minor exams. No compensation for missed exams except for medical reasons, in which case a doctor's certificate must be submited.
Major exam	40%

30% marks are necessary and sufficient for a passing grade, both in the credit as well as audit mode.

Academic Dishonesty Policy

The default penalty for academic dishonesty is as follows. If the concerned student chooses to audit the course, they get an NF. Else, the concerned student gets a zero for all answers that were obtained from illegitimate sources. Moreover, if their total marks make them eligible to get at least a B-, then they actually get a D; else, they get an F.