2015/16 Undergraduate Module Catalogue

COMP3910 Combinatorial Optimisation

10 creditsClass Size: 75

Module manager: Dr Natasha Shakhlevich
Email: N.Shaklevich@leeds.ac.uk

Taught: Semester 1 (Sep to Jan) View Timetable

Year running 2015/16

Pre-requisite qualifications

One of the pre-requisite modules must be studied.

Pre-requisites

COMP2421	Numerical Computation
COMP2711	Algorithms and Data Structures 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 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
Class tests, exams and assessment	1	2.00	2.00
Private study hours			66.00
Total Contact hours			34.00
Total hours (100hr per 10 credits)			100.00

Private study

Taught session preparation: 18 hours
Taught session follow-up: 18 hours
Self-directed study: 7 hours
assessment activities: 23 hours

Opportunities for Formative Feedback

Attendance and formative assessment.

Methods 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 website

Last updated: 05/11/2015

Disclaimer

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