PhD Qualifying Exam Information for Introduction for Optimization Theory

Rules:

  1. Students have four hours to complete the exam and submit their exam materials.  (Note: The 
    exam will be designed for an anticipated length of 2 hours, but we will allow four hours to 
    complete it.)
  2. The exam is open book and open notes.
  3. Students should bring a computer and software (e.g., AMPL/CPLEX) to solve linear programs and
    integer linear programs during the exam. If a student does not have access to a computer or
    software, they should let the graduate coordinator know at least 1 week before the exam.
  4. Students should bring a calculator or software capable of performing basic matrix operations.  If a student does not have access to a calculator or software, they should let the graduate coordinator know at least 1 week before the exam.
  5. Students may not access the Internet during the exam.
  6. Students may not communicate with others during the exam.

Exam Integrity:

  1. Within 24 hours of receiving confirmation that the exam materials have been received, students
    shall delete all files created during the exam and empty the trash/recycle bin on any devices
    used during the exam.
  2. When submitting their exam materials, students shall turn in all written work created during the
    exam.
  3. After completing the exam, students shall not communicate any information about the exam to
    anyone other than a member of the INEG faculty.

Suggested References:

  1. Introduction to Operations Research. Frederick S. Hillier and Gerald J. Lieberman, Tenth Edition.
    2015, ISBN-13: 978-1259162985.
  2. Operations Research: Applications and Algorithms. Wayne L. Winston, Fourth Edition. 2004,
    ISBN-13: 978-0534380588.
  3. Optimization in Operations Research. Ronald L. Rardin, Second Edition. 2017, ISBN-13: 978-
    0134384559.

Topics:

1.  Formulating models

      Be able to construct and/or identify an appropriate model given a problem description

  1. Mathematical programming
    1. Linear programming (LP) models
    2. Integer linear programming (ILP) models
    3. LP/ILP formulations of network optimization models
    4. Advanced modeling techniques (fixed-charge models, linearizable nonlinear functions, either-or constraints, etc.)
  2. Dynamic programming (i.e., define stages, states, and an optimality recursion)
  3. Formulating network optimization models (i.e., construct the network for a given problem)

2. Solving and Analyzing Mathematical Programs

    Be able to apply solution methods and important results
    Understand the reasoning behind, and implications of solution methods and important results
    Graphically interpret solution methods and important results
    Apply software (e.g., AMPL/CPLEX) to solve linear programs and integer linear programs

  1. Fundamental LP definitions and results (standard form, basic solutions, basic feasible
    solutions, unbounded/improving directions, characterizing extreme points, conditions
    for existence of an optimal extreme point)
  2. Exact LP solution methods (primal simplex algorithm, dual simplex algorithm)
  3. Duality (formulation, weak duality, strong duality, complementary slackness, dual simplex) and sensitivity analysis for LPs
  4. Exact IP solution methods (branch and bound, branch and cut)
  5. Definitions (efficient solutions, efficient frontier) and algorithms (weighted sums, constrained objectives) for multiobjective mathematical programs

3. Solving Dynamic Programs using Backward Dynamic Programming

    Be able to apply the solution method
    Understand the reasoning behind, and implications of the solution method

4. Solving and Analyzing Network Models

    Be able to apply the solution method and important results
    Understand the reasoning behind, and implications of the solution method and important results
    Be able to apply results from linear programming to those problems that can be formulated as LPs
    Understand relationships among the different classes of network optimization models

  1. Solution methods for transportation problems (transportation simplex algorithm, LP
    formulation)
  2. Solution methods for assignment problems (Hungarian algorithm, LP formulation)
  3. Solution methods for shortest path (Dijkstra’s algorithm, Bellman-Ford algorithm, LP formulation)
  4. Solution methods for maximum flow (augmenting path algorithm)
  5. Solution methods for minimum spanning tree (Kruskal’s algorithm, Prim’s algorithm)
  6. Solution methods for minimum cost flow (network simplex algorithm, LP formulation)