2016/17 Undergraduate Module Catalogue
COMP3910 Combinatorial Optimisation
10 creditsClass Size: 75
Module manager: Dr Natasha Shakhlevich
Email: N.Shakhlevich@leeds.ac.uk
Taught: Semester 1 (Sep to Jan) View Timetable
Year running 2016/17
Pre-requisite qualifications
One of the pre-requisite modules must be studied.Pre-requisites
| COMP2421 | Numerical Computation |
| COMP2711 | Algorithms I |
| COMP2941 | Algorithms II |
| MATH2210 | Introduction to Discrete Mathematics |
| MATH2640 | Introduction to Optimisation |
This module is not approved as a discovery module
Module summary
Understand how problems can be modelled as integer linear programs and solved using simplex based branch-and-bound. Appreciate the role of problem-specific heuristics in improving solution algorithms.Objectives
On completion of this module, students should be able to:- Understand the power and scope of linear programming and integer linear programming;
- Use other approaches to solve combinatorial optimisation problems and have an appreciation of the interaction between the solution process and problem formulation.
Learning outcomes
On completion of the year/programme students should have provided evidence of being able to:
-understand and demonstrate coherent and detailed subject knowledge and professional competencies some of which will be informed by recent research/scholarship in the discipline;
-deploy accurately standard techniques of analysis and enquiry within the discipline;
-demonstrate a conceptual understanding which enables the development and sustaining of an argument;
-describe and comment on particular aspects of recent research and/or scholarship;
-appreciate the uncertainty, ambiguity and limitations of knowledge in the discipline;
-make appropriate use of scholarly reviews and primary sources;
-apply their knowledge and understanding in order to initiate and carry out an extended piece of work or project.
Syllabus
- Linear programming: simplex method, duality and the dual simplex method;
- Integer Linear Programming: modelling of combinatorial optimisation problems and logical conditions;
- Solution by branch and bound;
- Network flow problems;
- Other solution approaches: construction and improvement heuristics.
Teaching methods
| Delivery type | Number | Length hours | Student hours |
| Example Class | 10 | 1.00 | 10.00 |
| Lectures | 22 | 1.00 | 22.00 |
| Private study hours | 68.00 | ||
| Total Contact hours | 32.00 | ||
| Total hours (100hr per 10 credits) | 100.00 | ||
Private study
Taught session preparation: 18 hoursTaught session follow-up: 18 hours
Self-directed study: 7 hours
assessment activities: 25 hours
Opportunities for Formative Feedback
CourseworkMethods of assessment
Coursework
| Assessment type | Notes | % of formal assessment |
| Problem Sheet | Problem Sheet 1 | 5.00 |
| Problem Sheet | Problem Sheet 2 | 5.00 |
| Problem Sheet | Problem Sheet 3 | 5.00 |
| Problem Sheet | Problem sheet 4 | 5.00 |
| Total percentage (Assessment Coursework) | 20.00 | |
This module is re-assessed by exam only.
Exams
| Exam type | Exam duration | % of formal assessment |
| Standard exam (closed essays, MCQs etc) | 2 hr 00 mins | 80.00 |
| Total percentage (Assessment Exams) | 80.00 | |
This module is re-assessed by exam only.
Reading list
The reading list is available from the Library websiteLast updated: 07/09/2016
Browse Other Catalogues
- Undergraduate module catalogue
- Taught Postgraduate module catalogue
- Undergraduate programme catalogue
- Taught Postgraduate programme catalogue
Errors, omissions, failed links etc should be notified to the Catalogue Team.PROD