Department of Industrial Engineering
4207 Bell Engineering Center
1 University of Arkansas
Fayetteville, AR 72701
Phone: (479) 575-3156
Fax: (479) 575-8431
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
- Be able to derive and execute the simplex algorithm
- Be able to state and prove:
- optimality conditions
- conditions leading to the elimination of degeneracy
- Be able to find starting solutions for the simplex algorithm
2. Duality Theory and Sensitivity Analysis
- Be able to demonstrate your understanding of the primal/dual relationship
- Be able to prove and apply weak and strong duality
- Be able to derive, prove and apply KKT Conditions
- Be able to explain the existence of shadow prices and reduced costs in the context of duality
3. Variants of the Simplex Method
- Be able to derive and execute the dual simplex algorithm
- Be able to derive and execute the primal-dual simplex algorithm
4. Decomposition and Large Scale Optimization
- Be able to derive and apply Dantzig-Wolfe decomposition
- Be able to derive and apply Benders decomposition
5. Interior Point Methods
- Be able to derive and apply Karmarkar’s algorithm
- Be able to derive and apply the affine scaling algorithm
- Be able to derive and apply the primal path following algorithm
- Be able to derive and apply the primal-dual path following algorithm
6. Complexity and Convergence of LP Solution Methods
- Be able to derive the complexity of the LP algorithms in Topics 1-5
- Be able to prove the convergence of the LP algorithms in Topics 1-5