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

MATH3017 Mathematical Programming

Module Overview

- Linear programs: their basic properties; the simplex algorithm. - Duality: the relationship between a linear program and its dual, duality theorems, complementarity, and the alternative; sensitivity analysis. - The interior point method for convex optimization: optimality conditions; the central path; convergence analysis; applications to linear programming and general convex optimization. - Integer Programming: Branch and bound algorithms and/or cutting plane methods. - The use of a computer software to solve mathematical programming problems.

Aims and Objectives

Module Aims

- Develop the ideas underlying linear and nonlinear convex optimization problems. - Describe and motivate the main algorithms to solve linear optimization problems. - Describe and motivate the interior point method and how to use it to solve convex optimization problems. - Develop the basic concepts in integer programming. - Overall, this module covers linear and nonlinear convex optimization problems, as well as integer programming problems; such problems arise in areas such as machine learning, engineering, manufacturing, distribution, finance, agriculture, health, energy and resources planning. - The introductory material on linear programming presented in MATH1058 and MATH2013 will be reviewed and some further properties developed. - The coursework involves formulating a mathematical programming model and solving it using a computer package.

Learning Outcomes

Learning Outcomes

Having successfully completed this module you will be able to:

  • Build a mathematical programming model of a real-life situation
  • Understand the basic theory and methods for linear programming problems
  • Understand the basic properties of the interior point method and how to use it to solve convex optimization problems
  • Apply branch and bound and/or cutting plane algorithms to solve integer programming problems
  • Use a computer package to solve a mathematical programing problem that arises in practice

Syllabus

- Linear programming: Basic applications of linear programming; basic concepts and properties of linear programming; the simplex method; duality and sensitivity analysis. - Convex optimization: model properties and some modern applications (e.g., in data science); Interior point method for linear programs (and some comparison with the simplex method); Interior point method for general convex problems. - Integer programming: Building integer programming models: examples with zero-one variables. General purpose branch and bound algorithm and/or the cutting plane method

Learning and Teaching

Teaching and learning methods

Lectures, computer workshops, problem sheets, private study.

TypeHours
Teaching52
Independent Study98
Total study time150

Resources & Reading list

HILLIER F S & LIEBERMAN G J, (2010). Introduction to Operations Research. 

R. Vandrbei (2014). Linear Programming: Foundation and Extension. 

SJ Wright (1997). Primal-dual interior-point methods. 

Assessment

Summative

MethodPercentage contribution
Coursework 20%
Exam  (2 hours) 80%

Referral

MethodPercentage contribution
Exam 100%

Repeat Information

Repeat type: Internal & External

Linked modules

Pre-requisite: MATH2013

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 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.

×