Department of Mathematicstheory
LINEAR OPTIMIZATION
MAT 4405
Syllabus
- 01Introduction to Linear Programming: Basic Solution, Hyperplane, Convex Polyhedron
- 02Simplex Method: Duality Theorem, Complementary Slackness, Farkes' Lemma, Revised Simplex Method
- 03General LP Problems: Infeasibility, Sensitivity Analysis
- 04Primal-Dual Algorithm: Applications to Network Flow and Matching
- 05Efficient Algorithm: Linear Programming in fixed dimensions, Randomized Linear Programming
- 06Integer Linear Programming: Total Unimodularity
- 07Semidefinite Programming: Application to MAXSAT problems
- 08Dynamic programming - Deterministic Dynamic programming, and probabilistic Dynamic programming
- 09Queuing systems, different types of queuing models, simulation models
- 10Finite Markov process and Markovian birth – death processes
References
- Bronson Richard - theory and Problems of Operations Research - Schaum series- MGH, 1983
- Hamdy A. Taha - operations Research (Ed.5) PHI, 1995
- Hiller and Liberman, Introduction to Operation Research, PHI, 1995
- V. Chavtal, Linear Programming, W. H. Freeman and Company, New York, 1983
- C. H. Papadimitriou and K. steiglitz, Combinatorial optimization: Algorithms and Complexity, Dover Publications, Inc., New York, 1998
- M. Grotschel, L. Lovasz and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, John Wiley & Sons, Inc., New York, 1998
- W. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Schrijver, Combinatorial Optimization, John Wiley & Sons, Inc., New York, 1998
- R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995
- David G. Luenberger, and Yinyu Ye Linear and Nonlinear Programming, Springer 2016
Credits Structure
3Lecture
0Tutorial
0Practical
3Total