Courses

DESCRIPTION
Decision making in many applications usually involves multiple conflicting criteria and uncertain factors. This course will cover these two important aspects of decision making. In the first half of the course, the theory of Multiple Criteria Decision Making (MCDM) and various approaches to deal with decision and optimisation problems with multiple criteria will be covered. In the second half of the course, optimisation under uncertainty, especially robust optimisation will be covered. Multi-objective optimisation under uncertainty which considers both aspects of multiple criteria and uncertainty in decision making will also be discussed.
Main contributors: Dr Banu Lokman (Course Leader), Dr Xuan Vinh Doan, Professor Dylan Jones

PRE-REQUISITES
The basics of mathematical programming

AIMS OF THE COURSE
The course aims to develop knowledge of decision making with multiple criteria and uncertainty and develop skills in building and solving optimisation problems with multiple objectives and uncertainty.

LEARNING OUTCOMES
On completion of the course, students will be expected to:
• Understand the properties of efficient solution alternatives in decision problems with multiple objectives
• Build and solve mathematical models to find nondominated solutions of multi-objective optimisation problems
• Understand and apply the goal programming method to solve decision problems with multiple goals
• Understand the concepts of optimisation under uncertainty
• Formulate and solve mathematical models for robust optimisation problems

PRINCIPAL TOPICS OF STUDY
• Introduction to Multiple Criteria Decision Making (MCDM)
• Efficiency and Nondominance
• Scalarization Techniques in Multi-objective Optimisation
• Exact & Approximate Solution Methods
• Goal Programming
• Introduction to Optimisation Under Uncertainty
• Robust Optimisation: Concepts and Reformulation
• Multi-Objective Optimisation Under Uncertainty

ASSESSMENTS
Assessment, a summative assessment exercise, will be held on the last day. It will typically last about an hour. Feedback will be provided before the end of the course.

OUTLINE
Day 1
12.30 – 13.30 Registration and lunch
13.30 – 15.00 Introduction to MCDM: Efficiency and Nondominance (Dr Banu Lokman)
15.00 – 15.30 Tea/Coffee Break
15.30 – 17.00 A Review of Linear and Integer programming (Dr Banu Lokman)

Day 2
9.00 – 10.30 Scalarization Techniques in Multi-objective Optimisation – Part 1 (Dr Banu Lokman)
10.30 – 11.00 Tea/Coffee Break
11.00 – 12.30 Scalarization Techniques in Multi-objective Optimisation – Part 2 (Dr Banu Lokman)
12.30 – 13.30 Lunch Break
13.30 – 15.00 Exact & Approximate Solution Methods (Dr Banu Lokman)
15.00 – 15.30 Tea/Coffee Break
15.30 – 17.00 Case Study 1: A Real-life Sales Territory Construction Problem (Dr Banu Lokman)

Day 3
9.00 – 10.30 Goal Programming: Theory and Applications – Part 1 (Professor Dylan Jones)
10.30 – 11.00 Tea/Coffee Break
11.00 – 12.30 Goal Programming: Theory and Applications – Part 2 (Professor Dylan Jones)
12.30 – 13.30 Lunch Break
13.30 – 15.00 Introduction to Optimisation under Uncertainty (Dr Vinh Doan)
15.00 – 15.30 Tea/Coffee Break
15.30 – 17.00 Review of Linear Duality (Dr Vinh Doan)

Day 4
9.00 – 10.30 Robust Optimisation – Part 1 (Dr Vinh Doan)
10.30 – 11.00 Tea/Coffee Break
11.00 – 12.30 Robust Optimisation – Part 2 (Dr Vinh Doan)
12.30 – 13.30 Lunch Break
13.30 – 15.00 Case Study 2: Robust Optimisation (Dr Vinh Doan)
15.00 – 15.30 Tea/Coffee Break
15.30 – 17.00 Multi-Objective Optimisation under Uncertainty (Dr Vinh Doan)

Day 5
9.00 – 10.00 Closing Session (Dr Banu Lokman)
10.00 – 11.00 Assessment
11.00 – 11.30 Round-up, feedback and farewell

This NATCOR course consists of two parts – the established system dynamics modelling short course and a new short course on behavioural modelling. The two parts are inter-related and it is recommended that students enrol in both, although it is also possible to enrol in either one of the two.

The course is run by academic staff from the University of Southampton, Konstantinos Katsikopoulos who chairs the OR Society’s SIG on Behavioural OR, and Martin Kunc who co-chairs the SIG on OR and Strategy. The two parts will be held back-to-back: First, the Behavioural OR part will focus on operational decision making, and then the System Dynamics part will focus on strategic decision making. Modelling is a common core for both parts, with Behavioural OR focusing more on mathematical modelling and System Dynamics focusing more on modelling and simulation. In addition to sessions by the course leaders and guest academics, there will also be sessions by external experts, including practitioners.

Description and value: Behavioural modelling

This two-and-a-half-day course is the first NATCOR course in Behavioural OR, and the first course in Behavioural OR in general, at least in the UK (Summer Schools have been held at the Universities of Aalto and Nijmegen). The course will focus on those domains of OR in which mathematical modelling has been mostly developing and yielding intellectual and practical benefits, including decision analysis, game theory, supply chain management and forecasting. The course will be founded on a key feature of behavioural science—the distinction among normative, descriptive and prescriptive models.

The course will be valuable to all of those OR students who have noticed the limits of approaches that are insensitive to how (i) human behaviour is modelled in models, (ii) clients interact with models and (iii) policy makers utilize models in their decision making—these aspects map to the Behavioural-OR taxonomy of behaviour in/with/beyond models. The course will be especially valuable to OR students looking to critically apply their skills and explore possibilities in areas adjacent to OR, such as economics and operations management, where human behaviour is since long being modelled. The sessions will be interactive, and there will also be plenty of time for informal interactions and networking.

Description and value: System modelling

Nowadays, there is an increasing integration of methods from economics and psychology in simulation that allow more rigorous approaches to address behavioural issues. One of these approaches is the use of laboratory and field experiments of individual and group decision making concerning human judgment and decision-making under uncertainty. System Dynamics, as a simulation methodology, has been employed successfully as a behavioural experimental tool as well as to represent bounded decision making. Some researchers suggest that System Dynamics models are behavioural models of business systems which uncover intended rationality (theories in use) in business decision making. The two and a half days will cover the basic principles of System Dynamics, System Dynamics to model behaviour, useful approaches to perform research using System Dynamics together with other OR methods.

Structure and content: Behavioural modelling TBC

Structure and content: Systems modelling TBC

Purpose
The Nottingham NATCOR course covers the main techniques for heuristic optimisation algorithms (local search, meta-heuristics, multi-objective heuristics, hyper-heuristics, evolutionary algorithms) as well as an insight into complexity theory, automated algorithm design, big data science and machine learning in the context of heuristic optimisation. The course is delivered by experts in the field with strong publication records and experience in the design and deployment of these methods on real-world problems in various business and industry scenarios.

Description
Heuristic Optimisation and Learning are cornerstone methodologies from the disciplines of Operational Research and Computer Science. These methods have been very successful in providing solutions to real-world problems across a wide range of application areas. Heuristic algorithms include a range of techniques from simple ‘rules of thumb’ to more sophisticated methods inspired on physical and natural processes like energy flow, evolution and swarm intelligence. Heuristics can provide good-quality solutions (although not necessarily optimal) in practical computational time to otherwise intractable problems. Heuristics can be applied and tailored to a wide range of optimisation problems. Heuristic algorithms can also be combined with exact optimisation algorithms to form a rich variety of hybrid methodologies capable of performing with high effectiveness and efficiency when tackling complex problems. Big data usually refers to data that has large volume, variety, and complexity so that specialised modern techniques are required in order to analyse it and extract valuable knowledge from it. With the widespread availability of big data in many research problems and real-world applications, learning from it presents more challenges than traditional data science. There are many facets of big data science including acquisition, storage, computing infrastructure, visualisation, security, privacy, analysis, mining, machine learning etc. There are exciting interactions between big data science, machine learning and optimisation, and one of these is learning from evolutionary algorithms which is one of the topics covered in this course.

The course is suitable for participants from a wide range of backgrounds, from those that are new to optimisation to those that already have knowledge in some of the main topics (optimisation, heuristics, evolutionary computation, big data science, machine learning) but want to learn about the other topics and their interactions. The course is also effective to provide a full picture of heuristic optimisation and its interactions to big data science and machine learning.

In terms of techniques, the course covers a good number of them, giving a comprehensive view of heuristic optimisation and learning. The course starts with a gentle introduction to the fundamentals of optimisation and complexity theory. It then moves to cover key concepts of constructive and local search heuristics. Then, the course studies some metaheuristic techniques and evolutionary algorithms focusing on the main mechanisms from the single and multi-objective perspectives. This is followed by sessions on hyper-heuristic techniques, their origins, classification and insights into variants of these methods. The course also includes sessions on big data science and machine learning as well as some of the links to optimisation with evolutionary algorithms. Other optimisation methods, like approximation algorithms and dynamic programming are also studied. Other topics covered in the course include the automated design of algorithms in the continuous and discrete spaces including topics like fitness landscape analysis, generalised pattern search and frameworks for algorithm design.

In terms of practice, the course describes the application of some of the optimisation and learning techniques covered in the course and others, to tackle real-world problems in areas like air transportation, airport operations, vehicle and personnel operational logistics, energy consumption prediction and others. Practical work with some of the techniques covered is also a feature of the course and participants are organised in teams to tackle a real-world challenge where optimisation and learning are applied. There are plenty of opportunities for course participants to network and discuss interests and ideas.

Delivery Method
Thanks to the current lifting of covid-19 restrictions in the UK, this course is planned to be delivered in-person. However, online tools like Microsoft Teams will also be used to enrich the learning experience and communication for course participants. Some course materials will be made available for downloading during the course.

The course will be delivered using a mix of lectures, discussions and practical work. For some parts of the course, participants will be asked to undertake some tasks individually or in groups and use some freely available or trial software. Emphasis will be put on making the course a rich experience where theory and practical work are blended. In addition to the instructors, there will be teaching assistants to help with managing the course and its logistics.

Pre-requisites
Basics of complexity and optimisation theory as well as computer algorithms and data structures. Some reading material is provided to students a couple of weeks in advance to the start of the course.

Aim
On completion of the course, students should have a working knowledge of the theory, design, implementation and application of the main heuristic methods, as well as an insight into their interplay with data science and machine learning in the context of optimisation scenarios.

Learning Outcomes
Understanding of the fundamental theory underlying the main heuristic optimisation methods (e.g. local search, metaheuristics, hyper-heuristics, evolutionary algorithms, etc.). Awareness of the strengths and limitations of different heuristic optimisation methods. Ability to critically evaluate the applicability and quality of different heuristic optimisation methods. Understanding the fundamentals of automated algorithm design in the continuous and discrete spaces. Capability for designing and developing heuristic methods for some optimisation problems. Awareness of some software tools for the rapid prototyping of heuristic optimisation methods. Understanding the fundamentals of data science and machine learning in the context of heuristic optimisation. Awareness of the key concepts in the application of some optimisation techniques to real-world airport and air transportation operations.

Assessment
A few formative assessments throughout the course in the form of quizzes and practical exercises, in addition to a simple summative test at the end of the course.

The summative test at the end of the course is in the format of multiple-choice questions spanning the various topics covered in the course. Undertaking this assessment is a requisite given the mechanism by which the delivery of the course is funded. However, it is emphasised that the degree of difficulty of this summative assessment in moderate. Engaging with the sessions and activities of the course should be sufficient to be able to do well in this assessment.

Previous Runs of the Course
The Nottingham NATCOR course has been delivered every two years since 2010. Each time as a residential course, except in 2020 when it was delivered online using Microsoft Teams due to the covid-19 pandemic. In past runs of the course, the number of participants has been between 50 and 90 and from several countries around the world. The course has attracted participants from diverse academic backgrounds including mathematics, business, computer science, industrial engineering, economics, statistics, operations management, management science, transportation logistics, psychology, etc. This is a course with a strong track record of success and being able to deliver it again in-person is a great excitement!

Some comments from previous participants in the course include the following:
“I really liked the practical session. It helped me to understand better the concepts explained in the lectures.”
“I think the course is very good and I benefit a lot especially from the meta-heuristic and practical sessions.”
“Well-organised in a logical way to connect all the ‘knowledge dots’ I had before into a clearer picture.”
“I really liked the course. It was very well organized and overall, very interesting. I liked how we were going deeper into the topics throughout the week, and mainly how the topics were so connected to the research of the lecturers.”

PRE-REQUISITES:

1. Undergraduate level knowledge of linear algebra (e.g. the relevant chapter in Winston’s textbook on OR) and calculus (e.g. basic notions of continuity and differentiability).
2. The students are expected to have familiarized themselves with the material marked with an asterisk in the teaching schedule and with other directed reading.

AIMS OF THE COURSE

1. To develop knowledge of different aspects of convex optimization and its applications.
2. To develop an ability to model real life problems as mathematical programming problems and an ability to adapt industry standard solvers to process them.
3. To develop an ability to analyze optimization algorithms for their merits and shortcomings.
4. To develop an ability to work independently as well as in a peer group with limited supervision.

LEARNING OUTCOMES FOR THE COURSE

The course provides opportunities for students to develop and demonstrate knowledge and understanding, qualities, skills and other attributes in the following areas:

(A) Knowledge and Understanding

On successful completion of this course, the students will have

1. knowledge of theoretical underpinning of convexity in optimization and of general nonlinear programming methods. This knowledge will act as a foundation to understand an advanced graduate textbook or a research paper without significant help.
2. understanding of linear programming methods and related theoretical issues.
3. knowledge of semi-definite programming.
4. ability to use an industry standard optimization software system for processing optimization models.

(B) Cognitive Skills

On successful completion of this course, the students will be able to

5. formulate realistic industrial problems as mathematical programming problems.
6. analyze critically the choice of algorithms for solving different classes of a particular optimization model regarding their computational effectiveness.
7. construct elementary proofs related to the properties of optimization methods.

(C) Other Skills and Attributes (Practical/Professional/Transferable)

On successful completion of this course, the students will be able to

8, plan and execute a solution to an optimization problem as a group and will be able to present the results to peers and tutors.

PRINCIPAL TOPICS OF STUDY:

Foundations of Convexity: affine and convex sets, convex functions, composition of convex functions.

General Convex Optimization: examples of convex optimization problems, duality, unconstrained minimization, steepest descent method, first and second order optimality conditions in unconstrained minimization, Newton’s method and convergence analysis, norm approximation problems.

Linear Programming: simplex method, duality for LP, interior point methods for LP.

Convex Quadratic Programming: simplex method for quadratic programming, application in finance, KKT conditions for convex QP.

Semi-definite Programming: formulation, extension of interior point methods to SDP, quadratically constrained convex quadratic programs.

A case study of convex optimization in industry.

Numerical Linear Algebra: algorithm complexity, Cholesky factorization, sparsity.

The latter part of this course will be run in two parallel streams: an application stream (A stream) and a theory stream (T stream). The lectures and workshops for the two streams will differ for the two streams for a part of the course, and the students will need to choose beforehand which stream they prefer to follow. Most of the topics of study are the same for both the streams, apart from the topics mentioned below:

A stream: Use of Industry Strength Solver Systems for LP/QP to process industrial problems.

T stream: advanced topics in optimization including interior point methods for convex quadratic optimisation, complexity analysis via self-concordance, interior point methods for second order cone programming, Nesterov’s method for smooth and non-smooth programming.

REFERENCES

[1] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004. As of June 2009, this text is freely available to download at http://www.stanford.edu/~boyd/cvxbook/ . The chapters relevant to this course are 2-5 and 9-11.
[2] D.G. Luenberger, Linear and Nonlinear Programming, Kluwer, 2003. The chapters relevant to this course are 2-10.
[3] R. Fourer, .M. Gay, B.W. Kernighan, Ampl: A Modeling Language for Mathematical Programming, Brooks Cole, 2002.
[4] Hillier and Lieberman, Introduction to Operations Research, McGraw Hill, 2002. The chapter relevant to this course is 13.

Predictive analytics and the methods of forecasting and data mining and are at the heart of almost all OR projects. Recent years have seen rapid developments in new methods, stimulated by increasing computing power and the growth of ‘big data’. The course’s objectives are to introduce students to these two key areas, important both for research and applications: data mining where the dramatic growth in data availability has meant new methods have been developed with many applications in OR, statistics and operations, and forecasting, which has a major role in many if not most OR modelling. In both these fields there have been many recent advances not least in the area of machine learning (building on data availability).

The first stage in any analysis of data is to explore the data to identify key components such as seasonality or to cluster the data to understand different segments (for example customer behaviour). After this introduction we then revisit regression, perhaps the single most used method for analysing multi-dimensional data. Here explanatory variables are linked through a model to the variable(s) of interest: various models of the data can then be developed and evaluated. Our emphasis is on model building rather than the mechanics of regression, which most participants will have been exposed to. Alternatively, where the aim is to understand the features of the data, these can be clustered into segments and the individual segments analysed to understand what features distinguishes one segment from another.

Where the data are collected over time, exploratory analysis of time series data decomposes the time series into certain key components such as trend and seasonality. simple models such as exponential smoothing have proved the workhorses of OR over many years. But often researchers will need to develop explanations of the forces that drive the focus variable. Regression (which most students have learnt something of) will be covered in some detail, both in its applications to model building including its use of testing theory but also in forecasting The type of application affects which methods are most suitable and lecturers will discuss how the nature of the data affects the choice of method. Finally, the course will examine the new methods of data mining and forecasting including neural networks, a flexible method which has the capacity to capture non-linearities in any data set.

Theoretical model building only takes us so far. The last two days of the course emphasize hands-on experience of these various methods through a group project analysing complex data. A short assessment of participants’ understanding completes the course.

The course assumes knowledge only of basic statistics. This course will be taught by members of Lancaster’s Centre for Marketing Analytics and Forecasting, led by Dr Nicos Pavlidis. The many data based exercises in the course rely on computer packages. We have chosen to use R which some but we quite understand not all of you will be familiar with it. But this is not a programming course. Participants will be given access to a self-learning course in R where participants can learn the basics quickly. But in exercises and the group workshops help will be at hand and the aim is for each group to include an R ‘expert’ to ensure that the analysis emphasizes model building rather than computing.

This course is supported by DataCamp

Dr Nicos Pavlidis: Course Leader
Dr Anna Srogonis: Course Coordinator
Dr Kandrika Pritularga: Course Coordinator

Timetable (to be confirmed)

Day 1 Monday
Start Finish
1:00:00 PM 1:30:00 PM Registration
1:30:00 PM 2:15:00 PM Welcome and Introduction: Predictive analytics and Forecasting
2:15:00 PM 2:45:00 PM Break
2:45:00 PM 3:30:00 PM Data Exploration & Decomposition
3:30:00 PM 4:15:00 PM Exercise
4:15:00 PM 4:20:00 PM Break
4:20:00 PM 5:05:00 PM Simple forecasting methods
6:30:00 PM 8:00:00 PM Social events, woodland walks

Day 2 Tuesday
Start Finish
9:00:00 AM 9:45:00 AM Intro to Forecasting
9:45:00 AM 10:30:00 AM Exponential smoothing
10:30:00 AM 11:15:00 AM Exercise (ETS)
11:15:00 AM 11:45:00 AM Break
11:45:00 AM 1:15:00 PM Forecast evaluation and selection​
1:15:00 PM 2:15:00 PM Lunch
2:15:00 PM 3:00:00 PM Exercise
3:00:00 PM 3:45:00 PM Autoregressive models
3:45:00 PM 4:15:00 PM Break
4:15:00 PM 5:00:00 PM Autoregressive models (tbc)
5:00:00 PM 5:45:00 PM ARIMA exercise

Day 3 Wednesday
Start Finish
9:00:00 AM 9:45:00 AM Regression modelling intro: Explanation and prediction
9:45:00 AM 10:30:00 AM Regression modelling II
10:30:00 AM 11:00:00 AM Break
11:00:00 AM 11:45:00 AM Exercise
11:45:00 AM 12:30:00 PM Dummy variables in regression
12:30:00 PM 1:30:00 PM Lunch
1:30:00 PM 2:15:00 PM Regression models for time series
2:15:00 PM 3:00:00 PM Exercise
3:00:00 PM 3:30:00 PM Break
3:30:00 PM 4:15:00 PM Classification: k-NNs, Cross validation
4:15:00 PM 5:00:00 PM Classification workshop
7:00:00 PM 9:00:00 PM Social dinner (Indian restaurant on China Street)

Day 4
Start Finish
9:00:00 AM 9:45:00 AM Introduction to Clustering
9:45:00 AM 10:30:00 AM Clustering Workshop
10:30:00 AM 11:00:00 AM Break
11:00:00 AM 11:45:00 AM Introduction to Artificial Intelligence/Machine Learning in Analytics;
11:45:00 AM 12:30:00 PM AI/ ML in Forecasting
12:30:00 PM 1:30:00 PM Lunch
1:30:00 PM 2:15:00 PM ML methods
2:15:00 PM 3:00:00 PM Workshop
3:00:00 PM 3:30:00 PM Break
3:30:00 PM 4:15:00 PM Group project
4:15:00 PM 5:00:00 PM Group project
5:00:00 PM 5:15:00 PM Break
5:15:00 PM 6:00:00 PM Group project

Day 5
Start Finish
9:00:00 AM 9:45:00 AM Group project
9:45:00 AM 10:30:00 AM Guest lecture (Alex)
10:30:00 AM 11:00:00 AM Break
11:00:00 AM 12:15:00 PM Group presentation
12:15:00 PM 12:45:00 PM Closing Remarks

Simulation is one of the most widely used operational research techniques. It involves the development of an imitation on a computer of the system under study, followed by experimentation to understand and investigate improvements to the system. This course provides an understanding of simulation, with a focus on the mathematical and statistical principles of stochastic simulation modelling. The main technique of interest is discrete-event simulation, although other simulation techniques will be introduced.

PRE-REQUISITES
An understanding of the basic principles of statistics including confidence intervals and hypothesis testing.
It would be useful to read some parts of the following books.

Statistical Aspects
Krzanowski, W.J. 2010. An Introduction to Statistical Modelling. Wiley, Chichester, UK.
Makridakis, S. Wheelwright, S.C. and Hyndman, R.J. 1998. Forecasting: Methods and Applications. 3rd ed., New York, Wiley.

Simulation Concepts
Pidd, M. (2005). Computer Simulation in Management Science, 5th ed. Wiley, Chichester, UK.Robinson, S. (2014). Simulation: The Practice of Model Development and Use. 2nd ed., Palgrave, UK.
Banks et al. (2010) Discrete Event System Simulation by (5th edition), Prentice Hall.
Law, A.M. (2015) Simulation Modeling and Analysis (5th edition).
Nelson, B.L. (2013) Foundations and Methods of Stochastic Simulation: A First Course.

Anylogic
Arash Mahdavi, The Art of Process-Centric Modeling with AnyLogic, http://www.anylogic.com/resources/books/the-art-of-process-centric-modeling-with-anylogic/

AIMS
The aim of the course is to provide an understanding of the mathematical and statistical principles of stochastic simulation modelling. The specific objectives are as follows:
• To understand the alternative simulation methods and the requirements for simulation studies
• To develop skills in simulation modelling and simulation computer packages
• To understand the nature of, and approaches to, input data modelling
• To be able to analyse the output from a simulation model using appropriate methods

LEARNING OUTCOMES
Subject Knowledge and Understanding
On completion of the course students will be expected to:
• Understand the basic principles of simulation and performing simulation studies.
• Understand the basic theory of simulation analysis including input data analysis, experimentation and output analysis.
• Understand the key stages in developing and using simulation models
• To be aware of the strengths and limitations of the approaches covered.

Intellectual Skills
On completion of the course students will be expected to:
• Be able to develop and use a simulation model for a given problem situation.
• Be able to evaluate the quality of a simulation analysis

Practical Skills
On completion of the course students will be expected to:
• Be familiar with the use of a simulation software package (Anylogic) as well code (Python) for DES modelling.
• Be able to follow an appropriate life-cycle for the development and use of simulation models

PRINCIPAL TOPICS OF STUDY

• basics of DES modelling
• modelling process
• input modelling
• model validation
• experimentation
• output analysis
• modelling in Python and Anylogic
• simulation optimisation
• simulation applications in industry and healthcare

COVERAGE OF WEB-BASED MATERIAL AVAILABLE IN ADVANCE
Material intended for preliminary reading discussing basics of the statistical aspects of simulation

A preliminary copy of the course timetable can be found here

Combinatorial optimisation problems typically involve finding the best arrangement, ordering, or selection of objects. There are numerous applications in Operational Research including scheduling of orders on machines in production industries, routing of vehicles to deliver goods to customers, and assigning of personnel such as nurses or airline crew to work periods. This course provides the main approaches and techniques required to tackle combinatorial optimisation problems. The main topics include computational complexity, types of algorithms, optimisation problems in networks, branch-and-cut, and branch-and-price.

Main contributors: Antonio Martinez-Sykora (University of Southampton), Trivikram Dokka (Lancaster University), Bo Chen (University of Warwick), Adam Letchford (Lancaster University), Chris Potts (University of Southampton), Stefano Coniglio (University of Southampton)

PRE-REQUISITES
The basics of linear and integer programming

AIMS
The course aims at providing an appreciation of the types of combinatorial problems that arise in Operational Research, and providing knowledge of the main approaches for tackling such problems.

LEARNING OUTCOMES
On completion of the course, the student will be expected to:

•understand the basics of complexity theory and be able to provide proofs that certain problems are NP-hard;
•have knowledge of a range of algorithms for shortest path, minimum spanning tree and network flow problems;
•analyse the worst-case running time of an algorithm;
•have an appreciation of the main types of approaches that can be used for tackling combinatorial optimization problems, together with their limitations;
•understand the principles behind branch-and-cut and branch-and-price, and be able to apply these approaches to new problems;
•have an overview of how combinatorial optimization techniques can be applied in an area such as data science.

PRINCIPAL TOPICS OF LEARNING
1.Introduction. Types of problems (for example, machine scheduling, vehicle routing and the travelling salesman problem, cutting and packing, set covering and partitioning).  Integer programming formulations.

2.Computational Complexity. Analysis of worst-case running time of algorithms (sorting, matrix multiplication, divide and conquer, dynamic programming). NP-completeness, reducibility.

3.Shortest path and minimum spanning tree algorithms.  Label setting shortest path algorithms (Dijkstra’s algorithm and its variants).  Label correcting shortest path algorithms (Bellman-Ford algorithm and its variants).  Greedy algorithms for the minimum spanning tree (Kruskal, Prim).

4.Network flow algorithms:  Maximum flow problem, augmenting paths, max-flow min-cut, Ford-Fulkerson algorithm and its variants.  Minimum cost flow problem.

5.General Solution Approaches.  Branch and bound, dynamic programming, constraint satisfaction, Lagrangean relaxation.

6.Branch and cut.  Valid inequalities, polyhedra and facets, separation, computational aspects.

7.Danzig Wolfe Decomposition.  Formulations using column generation, pricing algorithms, branching strategies.

8.Benders Decomposition.

9.Applications in Data Analysis and Visualisation.  Models from regression and classification, clustering and visualisation.