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 Introduction to Optimization Theory

**Rules:**

- 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.) - The exam is open book and open notes.
- 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. - 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.
- Students may not access the Internet during the exam.
- Students may not communicate with others during the exam.

**Exam Integrity:**

- 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. - When submitting their exam materials, students shall turn in all written work created
during the

exam. - 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:**

- Introduction to Operations Research. Frederick S. Hillier and Gerald J. Lieberman,
Tenth Edition.

2015, ISBN-13: 978-1259162985. - Operations Research: Applications and Algorithms. Wayne L. Winston, Fourth Edition.
2004,

ISBN-13: 978-0534380588. - 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*

- Mathematical programming
- Linear programming (LP) models
- Integer linear programming (ILP) models
- LP/ILP formulations of network optimization models
- Advanced modeling techniques (fixed-charge models, linearizable nonlinear functions, either-or constraints, etc.)

- Dynamic programming (i.e., define stages, states, and an optimality recursion)
- 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*

- 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) - Exact LP solution methods (primal simplex algorithm, dual simplex algorithm)
- Duality (formulation, weak duality, strong duality, complementary slackness, dual simplex) and sensitivity analysis for LPs
- Exact IP solution methods (branch and bound, branch and cut)
- Definitions (efficient solutions, efficient frontier) and algorithms (weighted sums, constrained objectives) for multiobjective mathematical programs

3. Solving Dynamic Programs

* Be able to apply a solution method of choice Understand the reasoning behind, and implications of the solution method you choose*

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*

- Solution methods for transportation problems (transportation simplex algorithm, LP

formulation) - Solution methods for assignment problems (e.g., Hungarian algorithm or, LP formulation)
- Solution methods for shortest path (e.g., Dijkstra’s algorithm, Bellman-Ford algorithm or, LP formulation)
- Solution methods for maximum flow (augmenting path algorithm)
- Solution methods for minimum spanning tree (e.g., Kruskal’s algorithm or, Prim’s algorithm)
- Solution methods for minimum cost flow (e.g., network simplex algorithm or, LP formulation)