Breadcrumb

Optimisation 3 (MATH 32500)

Contents of this document:

Administrative information
Unit aims, General Description, and Relation to Other Units
Teaching methods and Learning objectives
Assessment methods and Award of credit points
Transferable skills
Texts and Syllabus

Administrative Information

  1. Unit number and title: MATH 32500 Optimisation 3
  2. Level: 3
  3. Credit point value: 20 credit points
  4. Year: 2006-7
  5. First Given: 1993/4
  6. Lecturer/organiser: Dr. Y. Tourigny
  7. Teaching block: 2 (i.e., weeks 13 - 24)
  8. Timetable: Monday 12.10 pm, Thursday 11.10 am, Friday 12.10 pm
  9. Prerequisites: MATH 20600 Optimisation 2
  10. Examined in: May-June
  11. Unit Home Page:  http://www2.maths.bris.ac.uk/~mayt/MATH32500/

Unit aims

To introduce some ideas and methods in network, integer, and combinatorial optimisation, and develop expertise in using the methods on standard problems and extending the ideas to unseen types of problem; to develop students' ability to give mathematical formulations of optimisation problems.

General Description of the Unit

This unit follows on directly from the linear programming section of the Level 2 unit on Optimisation. A thorough knowledge of the simplex method is required.

The major themes are (i) review of linear programming, duality; applications in game theory; (ii) linear programming in network optimisation problems; (iii) extension of linear programming methods to integer programs; (iv) combinatorial optimisation. The focus will be on understanding the nature of the mathematical problems and developing methods for solving them. Mathematical theory for its own sake is not a feature of this unit; in this respect it is an "applied mathematics" unit.

The methods introduced in this unit are used regularly throughout business and industry.

Relation to Other Units

This unit is a sequel to Optimisation 2. Related (but different) material is in the Engineering Mathematics unit Nonlinear Optimisation and Dynamic Programming.  

NOTE that the Engineering Mathematics unit Introduction to Operations Research overlaps with the Mathematics units Optimisation 2 and 3.  So you can take this Engineering Mathematics unit only if you take neither Optimisation 2 nor Optimisation 3. 

Teaching Methods

Lectures, exercises to be done by students, use of computer software for solving optimisation problems.

Learning Objectives

After taking this unit, students should be able to:

  • use a range of standard methods to solve problems in network-related, linear, and integer optimisation;
  • discuss theoretical aspects of these methods, and modify and extend them;
  • outline some basic ideas of computational complexity, and recognise the distinctions between polynomial, non-polynomial, and NP problems;
  • formulate a range of combinatorial optimisation problems as integer programmes;
  • describe some standard heuristic methods for combinatorial optimisation problems, and devise new heuristic methods.

Assessment Methods

A 2h 30 min examination. FIVE questions, a candidate's FOUR best answers will be used for assessment. Candidates may bring one double-sided A4 sheet of notes into the examination. Calculators of an approved type are allowed.

Award of Credit Points

Credit points are gained by:

  • either passing the unit,
  • or getting an examination mark of 30 or over, and also handing in satisfactory attempts at four specified homework questions, to be given out at various times over the teaching block.

Transferable Skills

Analysing complex sets of conditions and formulating them mathematically; use of software to solve optimisation problems.

Texts

The recommended text is

  • W. L. Winston and M. Venkataramanan, Introduction to Mathematical Programming, Duxbury Press, 4th Edition 2003.

The following may also be useful:

  • H. P. Williams, Model Solving in Mathematical Programming, Wiley 1993
  • L. R. Foulds, Combinatorial Optimization for Undergraduates, Springer 1984 (particularly useful for the last section of the unit).

There are many other references; any recent book with a title like "Operations Research" is likely to be useful.

Syllabus

NOTE: The numbers of lectures given here are rough approximations only.

Review of linear programming, different formulations of the simplex tableau, duality theorems (3 lectures).

Further topics in linear programming: dual simplex and other methods; application of duality in game theory (5 lectures).

Maximum flow in a network; Ford-Fulkerson algorithm; flow/cut duality (3 lectures)

Transportation and transshipment problems. The network simplex algorithm (5 lectures)

Integer programming: problem formulation; general theory of IP; cutting-plane methods; branch & bound methods (8 lectures)

Combinatorial optimisation: knapsack and travelling salesman problems; NP and NP-complete problems (outline of ideas, not a full treatment); heuristic methods (6 lectures).