2022/23 Undergraduate Module Catalogue
COMP3910 Combinatorial Optimisation
10 creditsClass Size: 180
Module manager: Dr Natasha Shakhlevich
Taught: Semester 2 (Jan to Jun) View Timetable
Year running 2022/23
Pre-requisite qualificationsOne of the pre-requisite modules must be studied.
|MATH2231||Discrete Mathematics with Computation|
|MATH2640||Introduction to Optimisation|
This module is not approved as a discovery module
Module summarySolutions to many real world problems that arise in domains such as transport, manufacturing, supply chain management, telecommunications, financial decision making, healthcare logistics, planning and scheduling, can be obtained using techniques from the field of combinatorial optimisation. Combinatorial optimisation provides advanced analytical methods for decision making, where a set of feasible solutions is discrete and the task is to find the best one, with respect to some criteria. It is a well-established discipline with a powerful tool-kit that can be applied to solve real-world problems.In this module, we practice in formulating mathematical models using the techniques of linear programming and integer linear programming, learn how to distinguish between 'good' and 'bad' formulations and how the problems can be solved. One of the methods we study, the simplex method, is recognised as one of the 10 most influential algorithms of the 20th century.
ObjectivesThis module develops abstract modelling and problem solving skills and contributes to developing computer science professionals who are capable of handling real world problems using advanced analytical methods.
On successful completion of this module a student will have demonstrated the ability to:
- apply integer linear programming techniques to model combinatorial optimisation problems.
- select and apply appropriate methods for solving a combinatorial optimisation problem to find exact or heuristic solutions.
- articulate key concepts from the topic in a clear and rigorous manner.
This module covers the following 5 topic areas:
- Linear programming - simplex method, duality and the dual simplex method.
- Integer Linear Programming - modelling of combinatorial optimisation problems and logical conditions.
- Branch and bound algorithm - general methodology and implementation details.
- Network simplex algorithm - for minimum cost flows.
- Other solution approaches - construction and improvement heuristics.
|Delivery type||Number||Length hours||Student hours|
|Private study hours||68.00|
|Total Contact hours||32.00|
|Total hours (100hr per 10 credits)||100.00|
Private studyTaught session preparation: 10 hours;
Taught session follow-up: 10 hours;
Self-directed study: 13 hours;
assessment activities: 24 hours;
Opportunities for Formative FeedbackCoursework
Methods of assessment
|Assessment type||Notes||% of formal assessment|
|In-course Assessment||Coursework 1 (Gradescope)||10.00|
|In-course Assessment||Coursework 2 (Gradescope)||10.00|
|Total percentage (Assessment Coursework)||20.00|
Normally resits will be assessed by the same methodology as the first attempt, unless otherwise stated
|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 will be reassessed by exam only.
Reading listThe reading list is available from the Library website
Last updated: 01/06/2022 16:59:02
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