PhD Qualifying Exam Information for Linear Optimization

Materials Permitted:

  • 10 double sided hand written notes covering the topics below created by the student taking the exam.
  • Calculator.

Recommended Resources:

  • Linear Programming and Network Flows, Bazaraa, Jarvis, and Sherali, 2009
  • Introduction to Linear Optimization, Dimitris Bertsimas and John N. Tsitsiklis, 1997
  • Linear Programming, Vasek Chvatal, 1983

Recommended Topics:

1. The simplex method

  1. Be able to derive and execute the simplex algorithm
  2. Be able to state and prove:
    1. optimality conditions
    2. conditions leading to the elimination of degeneracy
  3. Be able to find starting solutions for the simplex algorithm

2. Duality Theory and Sensitivity Analysis

  1. Be able to demonstrate your understanding of the primal/dual relationship
  2. Be able to prove and apply weak and strong duality
  3. Be able to derive, prove and apply KKT Conditions
  4. Be able to explain the existence of shadow prices and reduced costs in the context of duality

3. Variants of the Simplex Method

  1. Be able to derive and execute the dual simplex algorithm
  2. Be able to derive and execute the primal-dual simplex algorithm

4. Decomposition and Large Scale Optimization

  1. Be able to derive and apply Dantzig-Wolfe decomposition
  2. Be able to derive and apply Benders decomposition

5. Interior Point Methods

  1. Be able to derive and apply Karmarkar’s algorithm
  2. Be able to derive and apply the affine scaling algorithm
  3. Be able to derive and apply the primal path following algorithm
  4. Be able to derive and apply the primal-dual path following algorithm

6. Complexity and Convergence of LP Solution Methods

  1. Be able to derive the complexity of the LP algorithms in Topics 1-5
  2. Be able to prove the convergence of the LP algorithms in Topics 1-5