Course Description:

Optimization problems occur in a wide variety of systems including communication systems, transportation systems, manufacturing systems and financial systems.  The main objective of the course is to provide students with a basic understanding of the optimization problems viz., the mathematical models, their formulation, and analysis and computational tools for their solutions.  This course covers major mathematical models of optimization problems -- linear programming, network flow, integer programming and nonlinear programming. We will focus on formulation issues and basic solution methodologies in a fairly rigorous fashion for these classes of optimization problems.

Prerequisites:

Reference Textbooks:

• "Introduction to Mathematical Programming", by F. S. Hillier and G. J. Lieberman, McGraw Hill, Seventh Edition, March 2002.

• "Introduction to Mathematical Programming", by W. L. Winston, Duxbury Press, Second Edition, 1997.

• "Operations Research: An Introduction", by H. A. Taha, Prentice Hall, Seventh Edition, July 2002.

Course Syllabus

 

1) Introductions and Simple Formulations
2) Linear Programming (LP)
2.1) Formulation and Assumptions of LP
2.2) Modeling and graphical method for LP
2.3) Simplex Method
2.4) Two-phase method
2.5) Big M method and special cases of the simplex method
2.6) Post-optimality analysis (Shadow prices and sensitivity analysis)
2.7) Duality theory
3) Network Analysis
3.1) Network flows
3.2) The Shortest Path problem
3.3) The Minimum Spanning Tree problem
3.4) The Maximum Flow problem
4) Integer Programming
4.1) Model and Formulation
4.2) Branch and Bound Algorithm
5) Nonlinear Programming
5.1) Convex sets and convex functions
5.2) Unconstrained optimization
5.3) Constrained optimization - basic ideas