Mathematical Programming I/ Optimization I (Tentative title)
-----------------------------------------------------------

Course Instructors: Saket Anand and Rajiv Raman
------------------

Eligibility: 3/4 yr BTech, MTech, PhD from ECE/CSE background
------------

Prerequisites:
--------------
Linear Algebra.

Post-Conditions:
----------------
Students will: 
- understand fundamental optimization problems, with emphasis on linear programs.
- learn how to model problems as optimization problems and use existing solvers to solve them.
- understand the concept of duality.
- develop working knowledge of using LP modeling languages (GAMS/AMPL) and solvers (CPLEX, Gurobi, etc.)

Course Description:
-------------------

Optimization is an important skill for engineers who are required to formulate a real-world problem into a mathematical program that can be solved numerically. Mathematical programming comprises of modeling of optimization problems followed by solving them. These techniques apply to both continuous as well as discrete settings, and are used widely across academia and industry.

This course aims at introducing students to the application of optimization techniques to various areas of CSE and ECE. We will primarily focus on linear optimization (linear programming) and learn about the structural and algorithmic aspects of optimization problems. The theoretical assignments will aim at developing the necessary skills for analysing algorithms and formulation of LPs. Computational assignments will  complement the theory by modeling real-world problems as linear programs and solve them using publicly available solvers. Towards the end of the course, if time permits, we will briefly discuss convex programs and semi-definite programs (SDPs) with real-world applications and point to some of the existing solvers for this class of problems. 


Tentative Topics:

Week 1: Introduction, Modeling and Applications
Week 2: Modeling and Applications (applications from CSE, ECE, comp. bio., economics) 
Week 3: Gaussian Elimination
Week 4: Graphical LP
Week 5: Simplex
Week 6: Simplex
Week 7: Theorems of the alternative
Week 8: Duality
Week 9: Duality, Sensitivity Analysis
Week 10: Interior Point methods/Ellipsoid method
Week 11: Network Flows
Week 12: SDPs
Week 13: Overflow

Evaluation:
-----------
Take home Assignments – 20%
Mid Term Exam – 40%
Final Exam – 40%

Recommended Textbooks: 
1. Introduction to Linear Optimization, Dimitris Bertsimas John N. Tsitsiklis. 
2. Linear Programming, Vasek Chvatal 
3. Understanding and Using Linear Programming, Jiri Matousek and Bernd Gartner is espeically nice.