Courses

DESCRIPTION
Multiple criteria decision making (MCDM) is a subfield of operational research that deals with the methods and tools to facilitate decision-making process in problems involving multiple conflicting criteria. It has applications in diverse domains such as business, supply chain, energy, healthcare, sustainability and logistics. This course will cover the theory of MCDM and various approaches to deal with decision problems with multiple criteria and tackle multi-objective optimisation problems.

Main contributors: Dr Banu Lokman (Course Leader), Professor Dylan Jones

PRE-REQUISITES
The basics of mathematical programming

AIMS OF THE COURSE
The course aims to develop knowledge of the theory of MCDM and develop skills in building and solving optimisation problems with multiple objectives.

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

PRINCIPAL TOPICS OF STUDY
• Introduction to multi-criteria decision making and classification.
• Efficiency and Nondominance
• Scalarization Techniques in Multi-objective Optimisation
• Exact & Approximate Solution Methods
• Goal Programming

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

OUTLINE
Day 1
12.30 – 13.30 Registration and lunch
13.30 – 14.40 Introduction to multi-criteria decision making.
14.40 – 15.00 Tea/Coffee Break
15.00 – 17.00 Efficiency and Nondominance. Definitions of Optimality.

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

Day 3
9.00 – 10.40 Goal Programming: Theory and Applications – Part 1
10.40 – 11.00 Tea/Coffee Break
11.00 – 12.30 Goal Programming: Theory and Applications – Part 2
12.30 – 13.30 Lunch
13.30 – 14.40 Discrete Choice Theory and Applications
14.40 – 15.00 Tea/Coffee Break
15.00 – 15.30 Assessment
15.30 – 16.40 Case Study 2: Goal programming and the Analytical Hierarchy Process (AHP) in the offshore wind sector
16.40 – 17.00 Concluding Remarks & Feedback Session

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

TIMETABLE

List of lecturers:
• Miguel Anjos (University of Edinburgh).
• Jacek Gondzio (University of Edinburgh).
• Julian Hall (University of Edinburgh).
• Lars Schewe (University of Edinburgh).
• Alper Yildirim (University of Edinburgh).

Course organizer: Sergio García Quiles (University of Edinburgh)

Sessions that are common to all the students are shown in black font.
Sessions only for the theory stream are shown in (blue).
Sessions only for the modelling stream are shown in (red).

Monday 6 June
13:00-14:00 Registration and welcome lunch
14:00-14:30 Welcome and introduction
14:30-16:00 (Julian Hall) Linear optimization
16:00-16:30 Coffee break
16:30-17:30 (Julian Hall) HiGHS: Open-source convex optimization software

Tuesday 7 June
9:30-11:00 (Alper Yildirim) Foundations of convexity
11:00-11:20 Coffee break
11:20-12:50 (Alper Yildirim) Role of convexity in optimization
12:50-14:20 Lunch (on your own)
14:20-16:20 (Jacek Gondzio) Interior point methods for linear programming (blue)
14:20-16:20 (Lars Schewe) Introduction to modelling with Xpress (red)

16:20-16:40 Coffee break
16:40-17:40 (Jacek Gondzio) Interior point methods for quadratic programming – Part 1 (blue)
16:40-17:40 (Lars Schewe) Modelling with Xpress (red)
18:30-21:00 Course Dinner

Wednesday 8 June
9:00-13:00 Guided tour and free time in Edinburgh
13:00-14:00 (Jacek Gondzio) Interior point methods for quadratic programming – Part 2 (blue)
14:00-15:00 (Jacek Gondzio) Interior point methods for second order cone programming (blue)
13:30-15:00 (Lars Schewe) Modelling with Xpress (red)
15:00-15:30 Coffee break
15:30-17:30 (Miguel Anjos) Introduction to conic and semidefinite Optimization. Max-cut formulations, relaxations and approximations

Thursday 9 June
9:30-11:00 (Alper Yildirim) Convex relaxations of nonconvex optimization problems
11:00-11:30 Coffee break
11:30-13:30 (Miguel Anjos) Semidefinite approaches for single-row facility layout. Polynomial optimization and the Lasserre hierarchy
13:30-15:00 Lunch (on your own)
15:00-16:00 (Julian Hall) Structure and matrix sparsity – Part 1
16:00-16:30 Coffee break
16:30-17:30 (Julian Hall) Structure and matrix sparsity – Part 2

Friday 10 June
9:00-10:00 (Lars Schewe) Xpress Presentations (red)
10:00-11:00 Lectures assessment (red)
9:30-11:00 Lectures assessment (blue)
11:00-11:30 Round-up, feedback and farewell

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

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).
• 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.