MTL508: Mathematical Programming

Course Syllabus

Linear programs formulation through examples from engineering / business decision making problems;
preliminary theory and geometry of linear programs, basic feasible solution;
simplex method, variants of simplex method, like two phase method and revised simplex method;
duality and its principles, interpretation of dual variables, dual simplex method, primal-dual method;
linear integer programs, their applications in real decision making problems, cutting plane and branch and bound methods, transportation problems, assignment problems, network maximum flow problems;
complexity of simplex method, ellipsoid method, Karmarkar’s interior point method;
nonlinear programming, Lagrange multipliers, Farkas lemma, constraint qualification, KKT optimality conditions, sufficiency of KKT under convexity;
quadratic programs, Wolfe method, applications of quadratic programs in some domains like portfolio optimization and support vector machines, etc.

Referenece Text Books

[We will not follow a single book. Appropriate references will be mentioned from this list.]

[R1] Linear Programming
by Howard Karloff

[R2] Understanding and Using Linear Programming
by Jiˇrí Matoušek and Bernd Gärtner

[R3] LINEAR PROGRAMMING and Network flows
by MOKHTAR S. BAZARAA, John J. Jarvis and HANIF D. SHERALI

[R4] NONLINEAR PROGRAMMING Theory and Algorithms
by MOKHTAR S. BAZARAA, HANIF D. SHERALI and C. M. SHETTY

[R5] Combinatorial Optimization: Algorithms and Complexity
by CH Papadimitriou and K. Steiglitz

[R6] Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties
by Alberto Marchetti-Spaccamela, Giorgio Ausiello, Giorgio Gambosi, Marco Protasi, Pierluigi Crescenzi, and Viggo Kann

[R7] Introduction to Linear Optimization
by Dimitris Bertsimas and John Tsitsiklis

[R8] Convex Optimization
by Stephen Boyd and Lieven Vandenberghe
Online version is here.

Other Resources on The Web

[W1]

Time and Place

3:30 PM to 5:00 PM on Monday and Thursday

LH 521, Lecture Hall Complex

Teaching Assistant

Priyamvada (Email: Priyamvada@maths.iitd.ac.in)

Weightage

Minor1: 25%; Minor2: 25%; Surprise Quiz: 15%; Major: 35%

Announcement

The second problem set is out. It's uploaded in the moodle.

Lectures

Lecture 1,2,3: Introduction

[date: 31st December, 3rd and 7th Jan] Formulation of Optimization Problems, Asymptotic Notations, Algorithms and Complexity Classes.

Reference: Sec 1.1 to 1.3 of R6;

Lecture 4: Introduction to Linear Programming (to be continued)

[date: 10th Jan] Different forms of LP, Examples, Graphical interpretation and solution; Solving piecewise linear convex objective function

Reference: Chap. 1 from R3, R7

Lecture 5: Basic Feasible Solutions (to be continued)

[date: 17th Jan]

Reference: Sec 1.5 from R7 , Sec 4.1-4.2 from R2

Lecture 6,7: Geometry of Linear Programming

[date: 19th and 21st Jan]

Reference: Sec 2.1-2.4 from R7, Sec 4.3-4.4 from R2

Lecture 8: Simplex Method (to be continued)

[date: 24th Jan]

Reference: Sec 3.1-3.2 from R7

Lecture 9: Revised Simplex Method

[date: 28th Jan]

Reference: Sec 3.3 from R7

Minor 1

Lecture 10: Two Phase Simplex Method

[date: 11th Feb]

Reference: Sec 3.5 from R7

Lecture 11: Duality Theorem (to be continued)

[date: 14th Feb]

Reference: Sec 4.1-4.2 from R7, Sec 6.1 from R2

Lecture 12,13: Dual Simplex Method

[date: 18th and 21st Feb]

Reference: Sec 6.4 from R3

Lecture 14: Primal Dual Method

[date: 23rd Feb]

Reference: Sec 6.5 from R3

Lecture 15: Shortest Path via Primal Dual Method

[date: 25th Feb]

Reference: Sec 5.4 from R5

Lecture 16, 17: Max Flow and Min Cut

[date: 28th Feb, 11th March]

Reference: Sec 6.1, 6.2 from R5

Lecture 18: Integer Linear Programmig: TUM

[date: 18th March]

Reference: Sec 13.2 from R5

Minor 2

Lecture 19: Integer Linear Programmig: Cutting plane, Branch-and-bound Algorithms

[date: 1st April]

Reference: Sec 14.1 from R5; Sec 11.1-11.2 from R7

Lecture 20: Dynamic Programming:TSP

[date: 4th April ]

Reference: Sec 11.3 from R7

Lecture 21: Dynamic Programming and Approximation Algo: Zero-one Knapsack Problem

[date: 5th April ]

Reference: Sec 11.3,11.5 from R7

Lecture 22: Introduction to Non-linear Programming

[date: 8th April ]

Reference: Sec 1.1,1.2, 4.1 from R4

Lecture 23: Lagrangian Multipliers and KKT Optimality Conditions

[date: 11th April ]

Reference: Sec 5.1,5.2, 5.5 from R8

Lecture 24: Quadratic Programming

[date: 15th April ]

Reference: Sec 4.4, 5.5 from R8,

Lecture 25: Complexity of Simplex: It is NOT a polynomial-time algorithm

[date: 18th April ]

Reference: Sec 8.6 from R5

Lecture 26: Ellipsoid Method

[date: 22nd April ]

Reference: Sec 8.2-8.4 from R7

Tutorial 1

[Date: 15th Jan]

question [by Priyamvada]

Tutorial 2

[Date: 21st Jan]

question [by Priyamvada]

Practise Problem Set

Will be uploaded on the moodle time to time.

LAB ASSIGNMENTS