Skip to main navigationSkip to main content
The University of Southampton
Courses

MATH6002 Deterministic OR Methods

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

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.

Learning Outcomes

Learning Outcomes

Having successfully completed this module you will be able to:

  • 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
  • model various condition-based constraints using binary variables and apply the branch and bound method to solve integer linear 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

TypeHours
Independent Study96
Teaching50
Workshops4
Total study time150

Resources & Reading list

HP Williams. Model Solving in Mathematical Programming. 

HP Williams. Model Building in Mathematical Programming. 

WL Winston. Operations Research: Applications and Algorithms. 

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

FS Hillier & GJ Lieberman. Introduction to Mathematical Programming. 

M Pinedo. Scheduling: Theory, Algorithms and Systems. 

V Chvatal. Linear Programming. 

Assessment

Assessment Strategy

The referral/repeat assessment includes both coursework and examination. If the coursework was previously passed, it is not retaken.

Summative

MethodPercentage contribution
Coursework 30%
Exam 70%

Repeat

MethodPercentage contribution
Coursework 30%
Exam 70%

Referral

MethodPercentage contribution
Coursework 30%
Exam 70%

Repeat Information

Repeat type: Internal & External

Share this module Share this on Facebook Share this on Google+ Share this on Twitter Share this on Weibo

We use cookies to ensure that we give you the best experience on our website. If you continue without changing your settings, we will assume that you are happy to receive cookies on the University of Southampton website.

×