- 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
Having successfully completed this module you will be able to:
- Build a mathematical programming model of a real-life situation
- Use a computer package to solve a mathematical programing problem that arises in practice
- Apply branch and bound and/or cutting plane algorithms to solve integer programming problems
- 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
- 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.
|Total study time||150|
Resources & Reading list
HILLIER F S & LIEBERMAN G J, (2010). Introduction to Operations Research. McGraw-Hill.
R. Vandrbei (2014). Linear Programming: Foundation and Extension. Springer.
SJ Wright (1997). Primal-dual interior-point methods. SIAM.
This is how we’ll formally assess what you have learned in this module.
This is how we’ll assess you if you don’t meet the criteria to pass this module.
Repeat type: Internal & External