I.E. 2082: LINEAR OPTIMIZATION 
(FALL 2017)

INSTRUCTOR:

Dr. Jayant Rajgopal
1032 Benedum Hall
Telephone No. 624-9840,
e-mail: rajgopal@pitt.edu

LECTURES:

Room 1045 Benedum Hall, Tuesdays and Thursdays, 11:00 AM to 12:15 PM.

TEXT:

There is no required text. The first reference by Griva, Nash and Sofer is an excellent text and is  strongly recommended for those who want to buy one; you can buy a reasonably priced on-line.  Lecture notes (in the form of copies of all overheads) are required - these will be made available for download from this site.

REFERENCES:

The following references will all be on reserve in the Engineering Library:
  1. Linear and Nonlinear Optimization, by Griva, Nash and Sofer
  2. Linear Programming and Network Flows, by Bazaraa, Jarvis, and Sherali
  3. Introduction to Linear Optimization, by Bertsimas and Tsitsiklis
  4. Linear Optimization and Extensions, by Fang and Puthenpura
  5. Linear Programming Foundations and Extensions, by Vanderbei
  6. Operations Research: Applications and Algorithms, by Winston and Venkatramanan

PREREQUISITES:

  1. Introductory course in Linear Programming/Operations Research and familiarity with the simplex algorithm.
  2. Knowledge of (a) linear algebra, (b) differential calculus, and (c) basic mathematical concepts such as sets, functions, vectors, matrices etc.
  3. An interest in mathematical methods.

CONTENT:

This is a Ph.D./advanced Master's level course meant for students who have already had an introduction to linear programming and the simplex method (typically, as part of an introductory operations research or management science course). It will examine some of the more advanced topics in this area. The primary emphasis will be on modeling and methodology (as opposed to formal theorems and proofs or specific applications of LP). However, a certain amount of requisite theory will be covered. The (tentative) list of topics includes the following: linear models, basic mathematical foundations and convex polyhedra, the (revised) simplex method; pricing and pivot selection mechanisms; generalized bounds; product form of the inverse; L-U factorization; duality and postoptimality analysis; dual simplex and primal-dual algorithms; Dantzig-Wolfe decomposition; column generation; special classes of linear programs; computational issues and analysis; interior-point methods including affine scaling and path-following algorithms. This list may be expanded or shortened depending on time constraints. Students are expected to make extensive use of the references in addition to the lecture notes.

GRADING:

Primarily on the basis of two examinations. Homework assignments will also be given.


HOMEWORK
HW1: Questions20 (Canadian Parks Commission), 61 (EJ Korvair) and 52 (paper recycling) from the Review problems at the end of Chapter 3 of the Winston text.  The book is on reserve in the library. (due Sep. 14)
  (SOLUTIONS)
Homework 2: Due Thursday, Sep. 21 (SOLUTIONS)
Homework 3: Due Thursday, Sep. 28 (SOLUTIONS)
Homework 4: Due Thursday, Oct. 12
Solutions to Exam 1
Homework 5: Due Thursday, Nov. 2
Homework 6: Due Tuesday, Nov. 14
Homework 7: Due Thursday, Nov. 30
Homework 8: Due Thursday, Dec. 07 (SOLUTIONS)

CLASS NOTES
Module 0

Geometry
Module 1

Module 2

Module 3

Module 4

Module 5

Module 6