The University of Southampton
Courses

MATH6161 Deterministic OR Methods for Data Scientists

Module Overview

This module aims to introduce the student to some of the main deterministic techniques that are used in operational research, namely linear and integer programming. 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.

Aims and Objectives

Module Aims

The aims of the module are: • To introduce the student to some of the main deterministic techniques that are used in operational research, namely linear and integer programming. • To introduce the student to the process of modelling problems of a practical nature as a linear or integer program. • To introduce a standard version of the simplex method, as well as some of its variants. • To explain the main ideas of linear programming duality. • Train the student in the use of commercial linear programming software. • To introduce the student to the branch and bound approach for solving integer programming problems.

Learning Outcomes

Learning Outcomes

Having successfully completed this module you will be able to:

  • formulate various problems using LP, IP and NLP
  • apply these steps to the two examples in the handout (and similar problems) (Section 1 (Intro to MP))
  • solve LP problems with two variables using the graphical method (Section 1 (Intro to MP))
  • write down general form and standard form of LP problems (Section 2 (Simplex Method))
  • transform LP problems from general form to standard form and vice versa (Section 2 (Simplex Method))
  • define basic solution, basic feasible solution, optimal BSF of LP problems in standard form (Section 2 (Simplex Method))
  • describe the idea behind the Simplex method (Section 2 (Simplex Method))
  • apply the dictionary and full tableau Simplex method to solve LP problems in standard form given a starting BFS (Section 2 (Simplex Method))
  • describe the method for finding initial BFS and to avoid cycling (Section 2 (Simplex Method))
  • describe the motivation for using duality and formulate the dual problem given the primal (Section 3 (Duality))
  • describe and prove week duality theorem (Section 3 (Duality))
  • describe graphical method, simplex methods (primal and dual) and apply them to solve relatively small LP problems
  • state LP duality theorem (Section 3 (Duality))
  • describe relationships for primal-dual pair in terms of optimality, feasibility and boundedness (Section 3 (Duality))
  • describe the dual Simplex method (using dictionary) (Section 3 (Duality))
  • describe complementary slackness conditions (Section 3 (Duality))
  • using duality and complementary slackness to verify optimality (Section 3 (Duality))
  • interpret shadow price and primal-dual pair in terms of profit maximization vs. resource scarcity (Section 3 (Duality))
  • describe situations when sensitivity analysis is used (Section 4 (Sensitivity))
  • derive the range of the RHS until the optimal basis start changing and the corresponding range of the optimal value (Section 4 (Sensitivity))
  • derive the range of the objective coefficient until the optimal basis start changing and the corresponding range of the optimal value (Section 4 (Sensitivity))
  • describe how dual simplex can be used in the case additional constraint leads to infeasibility (Section 4 (Sensitivity))
  • describe the motivation for using duality and formulate the dual problem given the primal
  • 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 4 (Sensitivity))
  • model either-or, set-up costs and other condition-based constraints using binary variables and constraints in the context of integer programming (Section 5 (Integer Programming))
  • formulate the knapsack problem using IP (Section 5 (Integer Programming))
  • derive (upper) bound on IP using LP relaxation (Section 5 (Integer Programming))
  • obtain (lower) bound on IP using rounding (Section 5 (Integer Programming))
  • describe general branch and bound method (Section 5 (Integer Programming))
  • apply branch and bound to solve simple IP (e.g. with no more than 3 variables) (Section 5 (Integer Programming))
  • describe duality theorems and complementary slackness
  • describe economic interpretation of shadow price and perform sensitivity analysis on LP
  • describe branch and bound methods
  • write the general form of a mathematical programming problem (Section 1 (Intro to MP))
  • distinguish between LP, IP, and NLP (Section 1 (Intro to MP))
  • describe 5 steps for formulating a mathematical programming problem (Section 1 (Intro to MP))

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.

Learning and Teaching

Teaching and learning methods

Five 2-hour lectures Two 1-hour class sessions Two 2-hour computer sessions

TypeHours
Completion of assessment task10
Practical classes and workshops6
Revision10
Lecture10
Follow-up work16
Wider reading or practice7
Preparation for scheduled sessions16
Total study time75

Resources & Reading list

FS Hillier & GJ Lieberman. Introduction to Mathematical Programming. 

V Chvatal. Linear Programming. 

WL Winston. Operations Research: Applications and Algorithms. 

HP Williams. Model Building in Mathematical Programming. 

HP Williams. Model Solving in Mathematical Programming. 

Assessment

Summative

MethodPercentage contribution
Coursework 30%
Exam 70%

Referral

MethodPercentage contribution
Exam  (2 hours) 100%

Repeat Information

Repeat type: Internal & External

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.

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.

×