Deterministic OR Methods | MATH6002 | University of Southampton

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

Having successfully completed this module you will be able to:

describe situations when sensitivity analysis is used and apply parametric programming when coefficients of the objective or the right hand side change
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
understand the basic principles of scheduling problems and corresponding solution methods
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

Study time
Type	Hours
Teaching	50
Independent Study	96
Workshops	4
Total study time	150

Resources & Reading list

Textbooks

V Chvatal. Linear Programming. Freeman.

M Pinedo. Scheduling: Theory, Algorithms and Systems. Prentice Hall.

HP Williams. Model Building in Mathematical Programming. Wiley.

HP Williams. Model Solving in Mathematical Programming. Wiley.

WL Winston. Operations Research: Applications and Algorithms. Duxbury.

S French. Sequencing and Scheduling: An Introduction to the Mathematics of the Job Shop. Ellis Horwood).

FS Hillier & GJ Lieberman. Introduction to Mathematical Programming. McGraw Hill.

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.

Breakdown
Method	Percentage contribution
Exam	70%
Coursework	30%

Referral

This is how we’ll assess you if you don’t meet the criteria to pass this module.

Breakdown
Method	Percentage contribution
Exam	70%
Coursework	30%

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.

Breakdown
Method	Percentage contribution
Exam	70%
Coursework	30%

Repeat Information

Repeat type: Internal & External