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

#### 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
Independent Study98
Teaching52
Total study time150

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

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

Recommended texts for this module may be available in limited supply in the University Library and students may wish to purchase reading texts as appropriate.

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.