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.

### 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:

• Module learning outcomes: By the end of this MP part, you would be able to… …formulate various problems using LP, IP and NLP …describe graphical method, simplex methods (primal and dual) and apply them to solve relative small LP problems. …describe the motivation for using duality and formulate the dual problem given the primal …describe duality theorems and complementary slackness …describe economic interpretation of shadow price and perform sensitivity analysis on LP …describe branch and bound methods Section 1 (Intro to MP) Learning Outcomes: By the end of this section, you would be able to… …write the general form of a mathematical programming problem …distinguish between LP, IP, and NLP …describe 5 steps for formulating a mathematical programming problem …apply these steps to the two examples in the handout (and similar problems) …solve LP problems with two variables using the graphical method Section 2 (Simplex Method) Learning Outcomes: By the end of this section, you would be able to… …write down general form and standard form of LP problems …transform LP problems from general form to standard form and vice versus …define basic solution, basic feasible solution, optimal BSF of LP problems in standard form …describe the idea behind the Simplex method …apply the dictionary and full tableau Simplex method to solve LP problems in standard form given a starting BFS …describe the method for finding initial BFS and to avoid cycling Section 3 (Duality) Learning Outcomes: By the end of this section, you would be able to… …describe the motivation for using duality and formulate the dual problem given the primal …describe and prove week duality theorem …state LP duality theorem …describe relationships for primal-dual pair in terms of optimality, feasibility and boundedness …describe the dual Simplex method (using dictionary) …describe complementary slackness conditions …using duality and complementary slackness to verify optimality …interpret shadow price and primal-dual pair in terms of profit maximization vs. resource scarcity Section 4 (Sensitivity) Learning Outcomes: By the end of this section, you would be able to… …describe situations when sensitivity analysis is used …derive the range of the RHS until the optimal basis start changing and the corresponding range of the optimal value …derive the range of the objective coefficient until the optimal basis start changing and the corresponding range of the optimal value …describe how dual simplex can be used in the case additional constraint leads to infeasibility …apply parametric programming to calculate the change of the objective value (and the optimal solutions) when more than one objective coefficient or the RHS are changed continuously Section 5 (Integer Programming) Learning Outcomes: By the end of this section, you would be able to… …model either-or, set-up costs and other condition-based constraints using binary variables and constraints in the context of integer programming …formulate the knapsack problem using IP …derive (upper) bound on IP using LP relaxation …obtain (lower) bound on IP using rounding …describe general branch and bound method …apply branch and bound to solve simple IP (e.g. with no more than 3 variables) Section 6 (Nonlinear Programming) Learning Outcomes: By the end of this section, you would be able to… …describe the general form of nonlinear programming problems …distinguish local and global minimum …define convex functions and convex sets …describe descent algorithm …state the necessary optimality condition in NLP …describe steepest descent algorithm

### Syllabus

Linear Programming. • Model construction and modelling issues. • Simplex method: two-phase algorithm, dual simplex method, network simplex method. • Duality: motivation and definitions, duality theorem, complementary slackness, optimality • testing. • Sensitivity analysis: ranging for objective function coefficients and right hand-side constraints, • economic interpretation and applications. • Parametric programming. Integer Programming. • Modelling techniques using zero-one variables. • Branch and bound algorithm for integer programming. • Applications of integer programming. Dynamic Programming. • Terminology including stages, states, recursion, principle of optimality. Examples involving shortest route problem, resource allocation problem, separable nonlinear programming problem, equipment replacement problem. • Probabilistic dynamic programming: illustrated by example in production planning. • Computational considerations. Machine Scheduling. • Introduction to scheduling models: machine environment, constraints on jobs, objective functions. • Use of adjacent job interchange argument to derive SPT and EDD rules. • Moore's algorithm for minimising the number of late jobs. • Scheduling with precedence constraints. • Dispatching rules for job shop scheduling: no idle and active schedule generation. Project Networks. • Drawing project networks. • Analysing project networks: earliest and latest event times, floats. • Critical path method. Time/cost trade-offs: linear programming solution, direct solution. Heuristics. • Design of heuristics: construction, relaxation, restriction, hierarchical decomposition, improvement. • Heuristics for the travelling salesman problem: nearest neighbour, savings, insertion, greedy. • Local search: neighbourhoods, simple descent, multi-start descent, iterated descent, simulated annealing, tabu search. Genetic algorithms: crossover, mutation

### Learning and Teaching

#### Teaching and learning methods

20 2-hour lectures 10 1-hour class sessions 2 2-hour computer sessions

TypeHours
Independent Study150
Total study time150

V Chvatal. Linear Programming.

M Pinedo. Scheduling: Theory, Algorithms and Systems.

HP Williams. Model Solving in Mathematical Programming.

FS Hillier & GJ Lieberman. Introduction to Mathematical Programming.

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

HP Williams. Model Building in Mathematical Programming.

WL Winston. Operations Research: Applications and Algorithms.

### Assessment

#### Assessment Strategy

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

#### Summative

MethodPercentage contribution
Coursework 30%
Exam 70%

#### Referral

MethodPercentage contribution
Exam  (2 hours) 100%

### Costs

#### Costs associated with this module

Students are responsible for meeting the cost of essential textbooks, and of producing such essays, assignments, laboratory reports and dissertations as are required to fulfil the academic requirements for each programme of study.

In addition to this, students registered for this module typically also have to pay for:

##### Books and Stationery equipment

Course texts are provided by the library and there are no additional compulsory costs associated with the module.

Please also ensure you read the section on additional costs in the University’s Fees, Charges and Expenses Regulations in the University Calendar available at www.calendar.soton.ac.uk.