Module overview
This module aims to introduce the student to the main deterministic techniques that are used in operational research, namely linear and integer programming, dynamic programming, machine scheduling, project networks, and heuristics. The process of modelling problems of a practical nature as a linear or integer program will be developed. Following an explanation of a standard version of the simplex method, some of its variants will be introduced. The main ideas of linear programming duality
will also be explained. A computer workshop session trains students in the use of commercial linear programming software. The branch and bound approach for solving integer programming problems will also be developed. Dynamic programming will be introduced as a technique for tackling problems in which decisions can be made sequentially. For machine scheduling, the main focus will be to introduce the main problem types, and develop solution procedures for selected models. For project networks, the representation of projects as networks and methods for analysing such networks will be covered. Following a discussion of the reasons for using heuristic methods for complex problems, a
discussion of the properties of good heuristics will be given. Some of the design principles for heuristics will be explained, and local search heuristics will be discussed.
One of the pre-requisites for MATH6158
Aims and Objectives
Learning Outcomes
Learning Outcomes
Having successfully completed this module you will be able to:
- understand the basic principles of scheduling problems and corresponding solution methods
- model various condition-based constraints using binary variables and apply the branch and bound method to solve integer linear programs
- formulate various problems using linear and integer programming, solve linear problems with the Simplex method, and have thorough understanding of duality theory, including the economic interpretation of dual programs
- describe situations when sensitivity analysis is used and apply parametric programming when coefficients of the objective or the right hand side change
- formulate various heuristics for hard combinatorial optimisation problems
Syllabus
- Linear Programming: model construction and modelling issues.
- Simplex method;.
- Duality: motivation and definitions, theory and economic interpretation;
- Sensitivity analysis and parametric programming;
- Integer programming: modelling techniques; branch and bound algorithm; Machine Scheduling: job constraints, precedence constraints, Moore’s algorithm;
- Heuristics: design, construction, relaxation, restriction, hierarchical decomposition, improvement.
- Local search algorithms;
Learning and Teaching
Teaching and learning methods
20 2-hour lectures
10 1-hour class sessions
2 2-hour computer sessions
| Type | Hours |
|---|---|
| Independent Study | 96 |
| Teaching | 50 |
| Workshops | 4 |
| Total study time | 150 |
Resources & Reading list
Textbooks
V Chvatal. Linear Programming. Freeman.
M Pinedo. Scheduling: Theory, Algorithms and Systems. Prentice Hall.
WL Winston. Operations Research: Applications and Algorithms. Duxbury.
HP Williams. Model Building in Mathematical Programming. Wiley.
FS Hillier & GJ Lieberman. Introduction to Mathematical Programming. McGraw Hill.
HP Williams. Model Solving in Mathematical Programming. Wiley.
S French. Sequencing and Scheduling: An Introduction to the Mathematics of the Job Shop. Ellis Horwood).
Assessment
Assessment strategy
The referral/repeat assessment includes both coursework and examination. If the coursework was previously passed, it is not retaken.
Summative
This is how we’ll formally assess what you have learned in this module.
| Method | Percentage contribution |
|---|---|
| Exam | 30% |
| Coursework | 70% |
Referral
This is how we’ll assess you if you don’t meet the criteria to pass this module.
| Method | Percentage contribution |
|---|---|
| Exam | 30% |
| Coursework | 70% |
Repeat
An internal repeat is where you take all of your modules again, including any you passed. An external repeat is where you only re-take the modules you failed.
| Method | Percentage contribution |
|---|---|
| Exam | 30% |
| Coursework | 70% |
Repeat Information
Repeat type: Internal & External