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

#### 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
Workshops4
Teaching50
Total study time150

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

V Chvatal. Linear Programming.

HP Williams. Model Solving in Mathematical Programming.

HP Williams. Model Building in Mathematical Programming.

M Pinedo. Scheduling: Theory, Algorithms and Systems.

WL Winston. Operations Research: Applications and Algorithms.

FS Hillier & GJ Lieberman. Introduction to Mathematical 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 70%
Exam  (2 hours) 30%

#### Repeat

MethodPercentage contribution
Coursework 70%
Exam  (2 hours) 30%

#### Referral

MethodPercentage contribution
Coursework 70%
Exam  (2 hours) 30%

#### Repeat Information

Repeat type: Internal & External