Courses

Below are details of our courses which will be running in the current academic year and details on how to apply.

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.

Due to the pandemic, the course will be held virtually via Microsoft Teams. 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

Monday (January 18, 2021)
10:30 – 11:00 Welcome and registration
11:00 – 12:30 Session 1: Foundations (normative/descriptive/prescriptive models and behaviour in/with/beyond models; Konstantinos Katsikopoulos)
12:30 – 13:30 Lunch
13:30 – 15:00 Session 2: Descriptive decision theory and some of its myths (hands-on group exercises and review of basic results; Konstantinos Katsikopoulos)
15:00 – 15:30 Coffee and tea
15:30 – 17:00 Session 3: Descriptive game theory (hands-on group exercises and review of basic findings; Zacharias Maniadis, Southampton Econ.)

Tuesday (January 19, 2021)
09:00 – 10:30 Session 4: The replication crisis in behavioural science (review of basic findings and theory; Thomas Gall, Southampton Econ.)
10:30 – 11:00 Coffee and tea
11:00 – 12:30 Session 5: Judgmental forecasting (hands-on group exercises and review of basic findings; Aris Syntetos, Cardiff PARC Institute of Manufacturing, Logistics and Inventory)
12:30 – 13:30 Lunch
13:30 – 15:00 Session 6: Behavioural OR in industry (Jon Malpass, British Telecom)
15:00 – 15:30 Coffee and tea
15:30 – 17:00 Session 7: Discussion with external experts and participants (“Now I can go ahead and apply Behavioural OR! Or not yet?”; moderated by Konstantinos Katsikopoulos)

Wednesday (January 20, 2021)
09:00 – 10:30 Session 8: Prescriptive decision analysis and some of its myths (hands-on group exercises and review of basic results; Konstantinos Katsikopoulos)
10:30 – 11:00 Coffee and tea
11:00 – 12:30 Session 9: Wrap-up and connection to System Dynamics (Konstantinos Katsikopoulos and Martin Kunc)
12:30 – 13:30 Lunch

Structure and content: Systems modelling

Wednesday (January 20, 2021)
13:30-15:00 Introduction to System dynamics software: from Vensim to R (Kunc)
15:00-15:30 Tea break
15:30-17:00 Rules for modelling and basic structures in System Dynamics (Kunc)
17:00-17:30 Summary for the Day – Q&A

Thursday (January 21, 2021)
9:00-10:30 Introduction to the system dynamics field (Morecroft)
10:30-11:00 Coffee break
11:00-12:30 Facilitated behavioural modelling: Using a simulator to examine investment dynamics (Morecroft)
12:30-13:30 Lunch
13:30-15:00 System dynamics and differential equations to represent behaviours (Morecroft)
15:00-15:30 Tea break
15:30-17:00 Research applications of system dynamics (Morecroft and Kunc)

Friday (January 22, 2021)
9:00-10:30 Optimisation in System Dynamics (Kunc and guest speaker – tba)
10:30-11:00 Coffee break
11:00-12:30 System Dynamics and Hybrid modelling (Kunc)
12:30-13:30 Lunch
13:30-15:00 System dynamics models using R (Duggan)
15:00-15:30 Tea break
15:30-17:00 Publishing articles using System Dynamics (Kunc)

Purpose
The Nottingham NATCOR course covers the main techniques for heuristic (local search, meta-heuristics, multi-objective heuristics, hyper-heuristics, evolutionary algorithms) and approximation 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.

Description
Heuristic and Approximation Algorithms are Operational Research tools that provide solutions to real-world optimisation 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 (though not necessarily optimal) in practical computational time to otherwise intractable problems. Heuristics can be applied and tailored to a wide range of optimisation problems. Approximation algorithms are designed to guarantee solutions of given quality based on worst-case analysis over all instances of the subject problem. These algorithms are designed for a specific problem or class of problems and can be useful as a rigorous method to study the performance of heuristics. 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 mains topics (optimisation, heuristics, approximation algorithms, big data science, machine learning) but want to learn about the other topics and their interactions. In day one, 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. In day two, the course continues with a session on the application of optimisation techniques to airport operations and a further session on complexity theory. It then moves to a study and demonstration of metaheuristic techniques focusing on the main mechanisms from the single and multi-objective perspectives. In day three, the course covers 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. The day ends with a session on introduction to evolutionary algorithms. Day four of the course starts with sessions on hyper-heuristic techniques, their origins, classification and insights into different types of hyper-heuristics. The second part of this day is dedicated to a practical session where the implementation of some heuristic optimisation algorithms is demonstrated. Day five of the course starts with sessions on big data science and machine learning as well as some of the links to optimisation with evolutionary algorithms. The course then closes with an introduction to approximation algorithms, dynamic programming and the application of some of the optimisation techniques covered in the course and others to improve real-world air transportation problems.

Delivery Method
Given the current restrictions due to the covid-19 pandemic, this course will be delivered online using Microsoft Teams. Guest access to the course environment will be arranged in advance by the course team. Although course materials including some pre-recorded videos will be made available for downloading, it will be essential that participants have Internet connection of sufficient quality to allow live video streaming as this will be used in some parts of the course.
The course will be delivered using a mix of pre-recorded lectures, live streamed sessions, online discussions and offline 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 although inevitably the online delivery will also present some challenges. In addition to the instructors, there will be teaching assistants to help with managing the course and its online delivery.

Pre-requisites
Basics of complexity and optimisation theory as well as computer algorithms. 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 applications of the main heuristic methods and approximation algorithms, 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 approximation algorithms and 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.

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 the NATCOR director, Professor John Boylan. It is (currently) envisaged to be made available both on-line or hopefully face-to-face. Its design is to ensure that participants do not experience unrelenting screen time. 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

Professor John Boylan: Course Leader
Dr Nicos Pavlidis: R Support Coordinator

Outline

Day 1
12.00 13.30 Registration and lunch
13.30 15.20 Introduction to data mining and forecasting
15.40 17.50 Regression modelling: explanation and prediction

Day 2
9.00 12.40 Exploratory data mining: clustering and classification
Lunch
13.30 15.30 Exploratory analysis of time series
15.45 17.30 Model evaluation and accuracy

Day 3
9.00 12.40 Autoregressive and other modelling frameworks
Lunch
13.30 15.30 Including policy interventions in time series models
15.45 17.30 Regression modelling for time series

Day 4
9.00 10.30 Regression modelling for time series
10.50 12.40 Introduction to AI and ML in forecasting
Lunch
13.30 15.30 Group project
15.50 17.30 More on ML methods

Day 5
9.00 10.40 Group project and presentations
11.00 12.00 Multiple choice assessment
12.00 13.15 Summing up

Stochastic Modelling is concerned with using probability concepts and techniques for capturing uncertainty in order to describe situations, predict performance and support decision making. Many activities in real-life situations are not deterministic in nature, but rather have an unknown or uncertain element attached to them. The Operational Research literature abounds with applications of Stochastic Modelling, with Healthcare, Transportation, Computing and Communications, Business and Finance being just a few examples. In the recent years, Stochastic Modelling has become a key component of interdisciplinary research between Operational Research and Statistics and Machine Learning.

This course will present some of the theory behind such modelling processes, but consideration will also be given to applications by means of case studies. The topics covered are: Stochastic Processes, Queueing Systems and Networks, Maintenance and Reliability, Inventory Control and Revenue Management. This course will be taught by members of Lancaster University, especially from its research groups on Simulation and Stochastic Modelling, Optimisation and Centre for Transport & Logistics, complemented with speakers from other institutions and companies. It will run fully online, in a blended way including interactive sessions, and there will also be plenty of time for informal interactions and networking.

Dr. Peter Jacko: Course Leader

PRE-REQUISITES
Much of the material needed as background reading for this course will be provided on-line. The preparatory material will cover basics of probability, random variables, probability distributions and stochastic processes, and introductions to maintenance & reliability, queueing theory, inventory control and revenue management.

AIM
The course aim is to provide an appreciation of the theory which has been developed to model real-life situations using probability concepts and techniques. On completion of the course, participants should be better prepared to understand the more sophisticated models that appear in the literature.

LEARNING OUTCOMES
On completion of the course, students will be expected to:
– understand the basics of probability concepts and techniques, with particular relevance to queueing systems and networks, maintenance and reliability, inventory control and revenue management
– be aware of the rich diversity of scenarios to which stochastic modelling may be applied,
– be conscious of the relationships and complementarities between analytic and simulation modelling.

PRINCIPAL TOPICS OF STUDY
Stochastic Processes: Markov chains, Markov processes, finitely many states, continuous-time chains, random walks, branching processes, renewal processes.
Queueing Systems and Networks: Queues with general arrival and service patterns, queues in series and in parallel, batch arrivals and services, phase-type service distributions, numerical approaches to transient behaviour.
Maintenance and Reliability: Replacement decisions (age, preventative, block, etc), inspection criteria, stochastic comparisons of system reliabilities and maintenance policies, scheduling and sequencing decisions, continuous and discrete renewal and repair processes and their computational requirements.
Inventory Control: Review of deterministic models as approximations to stochastic situations, Newsboy-type problems, time-varying demands, stochastic demand with constant lead-times, stochastic lead-times.
Revenue Management: stochastic modelling of demand, models of perishable products, strategies of decisions making, discrete-time Markov decision processes, stochastic dynamic programming algorithms, curse of dimensionality, optimisation/learning trade-off.
Case studies. The above topics will be illustrated by case studies of applications from fields such as business and finance, computing and communications, transportation, or healthcare.

ASSESSMENTS
Assessments, which will be formative in nature, will be held each day. They will take a variety of formats, and will typically last about half-an-hour. Feedback will be provided before the end of the course.

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.

DELIVERY METHOD
Given the current restrictions due to the covid-19 pandemic, this course will be delivered online using Microsoft Teams. Guest access to the course environment will be arranged in advance by the course team. Although course materials including some pre-recorded videos will be made available for downloading, it will be essential that participants have Internet connection of sufficient quality to allow live video streaming as this will be used in the course.
The course will be delivered using a mix of pre-recorded lectures, live streamed sessions, online discussions and offline 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 although inevitably the online delivery will also present some challenges. In addition to the instructors, there will be teaching assistants to help with managing the course and its online delivery.

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).
• Be able to follow an appropriate life-cycle for the development and use of simulation models

PRINCIPAL TOPICS OF STUDY
• Simulation methods and simulation software
• Discrete-event simulation: how it works
• Simulation studies and the simulation modelling life-cycle
• Model validation
• Input Modelling
• Output Analysis
• Analysis of a single scenario – obtaining accurate results
• Basics of comparing multiple scenarios
• Experimental Design and Analysis
• Data analysis methods in Simulation Modelling
• Basic model estimation and model fitting
• Modelling input uncertainty
• Metamodelling
• Simulation optimisation
• Bootstrapping

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

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.

SECURE YOUR PLACE TODAY