## COMP3910 Combinatorial Optimisation

### 10 creditsClass Size: 180

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

Taught: Semester 2 (Jan to Jun) View Timetable

Year running 2021/22

### Pre-requisite qualifications

One of the pre-requisite modules must be studied.

### Pre-requisites

 COMP2421 Numerical Computation COMP2711 Algorithms I COMP2721 Algorithms II MATH2230 Discrete Mathematics MATH2231 Discrete Mathematics with Computation MATH2640 Introduction to Optimisation

This module is not approved as a discovery module

### Module summary

Solutions 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.

### Objectives

This 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.

Learning outcomes
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.

### Syllabus

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.

### Teaching methods

Due to COVID-19, teaching and assessment activities are being kept under review - see module enrolment pages for information

 Delivery type Number Length hours Student hours Consultation 10 1.00 10.00 Lectures 22 1.00 22.00 Tutorials 10 1.00 10.00 Private study hours 58.00 Total Contact hours 42.00 Total hours (100hr per 10 credits) 100.00

### Private study

Taught session preparation: 10 hours;
Taught session follow-up: 10 hours;
Self-directed study: 13 hours;
assessment activities: 24 hours;

This module is re-assessed by exam only.

Coursework

### Methods of assessment

Due to COVID-19, teaching and assessment activities are being kept under review - see module enrolment pages for information

Coursework
 Assessment type Notes % of formal assessment In-course Assessment Coursework 1 (Gradescope) 10.00 In-course Assessment Coursework 2 (Gradescope) 15.00 In-course Assessment Coursework 3 (Gradescope) 15.00 In-course Assessment Engagement in homework - Submissions throughout the semester as part of tutorial preparation 5.00 In-course Assessment Stretch exercises - Submissions throughout the semester as part of tutorial preparation 5.00 Total percentage (Assessment Coursework) 50.00

This module will be reassessed by an online time-constrained assessment.

Exams
 Exam type Exam duration % of formal assessment Online Time-Limited assessment 48 hr 00 mins 50.00 Total percentage (Assessment Exams) 50.00

This module will be reassessed by an online time-constrained assessment.