Courses

Below are details of our courses which will be running in the year 2017/18 and details on how to apply.

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: Tolga Bektas (University of Southampton), Trivikram Dokka (Lancaster University), Bo Chen (University of Warwick), Adam Letchford (Lancaster University), Chris Potts (University of Southampton), Dolores Romero (Copenhagen Business School), Vladimir Deineko (University of Warwick)

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.

Introduction

The two-and-a-half day course will focus on the principles of time-series forecasting, and recent developments in predictive analytics. Many examples will be used and there will be opportunities for participants to use models ‘hands-on’ and to experiment with real data. Links between forecasting, predictive analytics and decision making under uncertainty will be emphasised. The relevance of forecasting to non-stationary environments will be discussed, for example in inventory, simulation and optimisation models.

Location and Session Leaders

Sessions will be led by experts from the Lancaster Centre for Forecasting, calling on external experts if necessary. The overall co-ordinator will be Professor John Boylan.

Course Structure

The course will be subdivided into three sections, as follows:

•Time series modelling

 

•Econometric models

 

•Predictive analytics

 

This forms a natural sequence, moving from univariate models to classical multivariate models to modern methods which address both univariate and multivariate data.

The session on time series modelling will commence with the simplest methods, with opportunities for participants to experiment with parameter choices and to appreciate the scope for parameter optimisation methods to improve forecast accuracy. Model-based approaches will be covered, as well as criteria for choosing between forecasting models. A more general discussion will be held on error measurement and concerns about the reproducibility of forecasting research.

The session on econometric models will start with an introduction to the concepts involved, but will assume some knowledge of regression modelling. It will cover diagnostic analysis of regression models and model choice. This session will also cover some of the important technicalities of econometric time-series models, such as spurious regression, cointegration and modelling non-stationary data. It will conclude with a broader discussion of asymmetric loss functions and forecaster behaviour.

The final session on predictive analytics will cover some key topics for time series analysis. This will include data mining, with a focus on time series clustering for data exploration, and time series classification. It will also cover artificial intelligence for forecasting, focussing on Artificial Neural Networks and recent developments in ensemble methods for forecasting.

Day 1

The initial half-day is devoted to learning the most used System Dynamics software: Vensim, in a laboratory. Initially a simple model to familiarise with the existing components of System Dynamics is offered. Then, rules for modelling and basic structures in System Dynamics are taught using relevant examples in the laboratory.
The objective of the day 1 is to offer students a solid base to start modelling using System Dynamics..

PRELIMINARY READINGS

Software requirements
• Vensim PLE Software Download link and brief intro to the simulation software– Please, read the document, install the software in your laptop and follow the brief exercise.
• Selected readings from Sterman (200) Business Dynamics, McGraw Hill.

Please note that preliminary reading will be available on-line in advance of the course.

PRINCIPAL TOPICS OF STUDY

Introduction to System Dynamics

We start with a brief introduction to the main software to develop System Dynamics model: Vensim. The basic building blocks of system dynamics modelling are introduced. We then use modelling and simulation to explore common structures in System Dynamics. A workshop in the laboratory provides hands-on experience of a simulator and the software used to create it.

FOLLOW-UP READINGS

• Gary, S, Kunc, M, Morecroft J and Rockart, S. 2008. System Dynamics and Strategy. System Dynamics Review 24: 407–430
• Kunc, M. 2016.
• Kunc, M. 2017.

Day 2

The purpose of this day is to introduce to system dynamics (SD) and illustrate its use within the field of operational research, to develop models about the strategic end of operations.  The day includes lectures, simulation workshops and a selection of applied research topics.

During the course as-a-whole students will learn enough about system dynamics to appreciate how it might apply to their own research interests. Options for follow-up courses will also be discussed.

PRELIMINARY READINGS

• Forrester (1995) The beginning of system dynamics, McKinsey Quarterly, 1995, 4, 4-16.
• iThink 10.1 Software Download Link – Please, read the document and install the software in your laptop.

Please note that preliminary reading will be available on-line in advance of the course.

PRINCIPAL TOPICS OF STUDY

Introduction to System Dynamics

We start with a brief history of system dynamics and the feedback view of firms and society.  The basic building blocks of system dynamics modelling are introduced.  We then use modelling and simulation to examine long term dynamics of investment decision making.  A workshop provides hands-on experience of a simulator and the software used to create it.

System Dynamics and Differential Equations

A workshop to build and interpret a tiny system dynamics model whose cyclical dynamics are equivalent to the sinusoidal solution of a second-order linear differential equation.  The model illustrates a key idea in SD that ‘feedback structure gives rise to dynamic behaviour’.

Research Applications of System Dynamics

A glimpse of published research that applies system dynamics modelling and simulation to corporate diversification, an important topic in the strategy area.  Then there is a discussion of how to communicate model-based simulation studies to other academics.

FOLLOW-UP VIDEO

• Video:  Morecroft (2009), Reflections on System Dynamics and Strategy, a lecture originally delivered at Worcester Polytechnic Institute WPI in Massachusetts.  The lecture is now on YouTube and can be found by Googling ‘System Dynamics and Strategy’.

FOLLOW-UP READINGS

• Morecroft (1999), Management attitudes, learning and scale in successful diversification, Journal of the Operational Research Society, 50, 4, 315-336.
• Repenning (2003), Selling system dynamics to (other) social scientists, System Dynamics Review, 19, 4, 303-327.
• Kunc and Morecroft (2010), Managerial Decision-Making and Firm Performance Under a Resource-Based Paradigm,

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.

Heuristics and Approximation Algorithms are Operational Research tools that provide solutions to real-world problems across a wide range of application areas despite their inherent complexity and uncertainty. Heuristics are ‘rules of thumb’ and other clever algorithms that despite being relatively simple to implement can provide good (though not necessarily optimal) and fast solutions to otherwise intractable problems. This course features the main techniques and also practical sessions, so that participants leave with the capabilities to start implementing their own heuristics.

PRE-REQUISITES

TBA soon

AIM

On completion of the block, the student should have a working knowledge of the theory, applications and implementation issues of the main heuristic approaches to combinatorial optimization and their practical application.

LEARNING OUTCOMES

Knowledge and Understanding
On completion of the block, the student will be expected to
•understand the basic theory underlying the main heuristic approaches to optimization, such as local search, genetic algorithms and their variants;
•be aware of the strengths and limitations of each approach.

Intellectual Skills
On completion of the block, the student is expected to give evidence of the following intellectual skills
•be able to critically evaluate the quality of different heuristic optimization approaches;
•be capable of applying their knowledge and understanding to develop an appropriate heuristic for a new problem.

Practical Skills
On completion of the block, the student is expected to have developed the following subject-specific practical skills
•be familiar with at least one software tool in the area;
•be able to apply an appropriate range of optimization heuristics to a given problem.

CONTENTS

1. Heuristics
What are heuristics? Classification of heuristic search, When to use heuristic search? Local search, Design of local search algorithms (representation of solutions, neighbourhood, search process, escaping from local optima, Multistart Local Search, GRASP, Variable Neighbourhood Search), Constraint handling, Parameter tuning, Analysis of heuristic search performance, Complexity theory

Meta-Heuristic approaches

2. Simulated Annealing – Basic concepts, Algorithm, Practical considerations (initial temperature, equilibrium state, cooling schedule, stopping condition), Simulated Annealing inspired algorithms (Threshold Accepting, Great Deluge Algorithm)

3. Tabu Search – Basic concepts, Algorithm, Memories (short-memory, intermediate memory, long term memory), Diversification techniques, Practical considerations

4. Evolutionary Computation – Basic concepts, Components of Evolutionary Computation, Classification of Evolutionary Computation algorithms, Genetic Algorithm, Practical considerations

5. Approximation Algorithms

6. Multiobjective Evolutionary Algorithms – Basic concepts, Multiobjective applications, Classification, Evolutionary Multiobjective Optimisation (fitness assignment, diversity preserving, elitism), Weighted Sum Approach, VEGA, Procedure for finding the approximation of Pareto set, NSGA-II, Performance evaluation

7. Real-world problems solved by heuristics/meta-heuristics

8. Lab session (4 hours)

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. (2001) Discrete Event System Simulation by (3rd edition), Prentice Hall. (Chapter 12)
• Law (2006) Simulation Modeling and Analysis (4th edition). (Chapters 10-12)

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 (SIMUL8).
• Be able to follow an appropriate life-cycle for the development and use of simulation models
• Be familiar with the use of statistical analysis software (e.g. Excel, Minitab, SPSS).

PRINCIPAL TOPICS OF STUDY
1. Principles of Simulation
1.1 Introduction to simulation methods (Monte Carlo, discrete-event, system dynamics and agent based simulation) and simulation software
1.2 Generating random variates
1.3 Computing aspects of simulation
1.4 Simulation studies and the simulation modelling life-cycle
1.5 Model validation
2. Random Sampling
2.1 Random number generation
2.2 Sampling from distributions
2.3 Variance reduction methods
3. Introduction to Output Analysis
3.1 Analysis of a single scenario – obtaining accurate results
3.2 Basics of comparing multiple scenarios
4. Experimental Design and Analysis
4.1 Time series analysis
4.2 Experimental design
4.3 Metamodelling
4.4 Simulation optimisation
4.5 Bootstrapping (for input data modelling as well)

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

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. (2001) Discrete Event System Simulation by (3rd edition), Prentice Hall. (Chapter 12)
• Law (2006) Simulation Modeling and Analysis (4th edition). (Chapters 10-12)

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 (SIMUL8).
• Be able to follow an appropriate life-cycle for the development and use of simulation models
• Be familiar with the use of statistical analysis software (e.g. Excel, Minitab, SPSS).

PRINCIPAL TOPICS OF STUDY
1. Principles of Simulation
1.1 Introduction to simulation methods (Monte Carlo, discrete-event, system dynamics and agent based simulation) and simulation software
1.2 Generating random variates
1.3 Computing aspects of simulation
1.4 Simulation studies and the simulation modelling life-cycle
1.5 Model validation
2. Random Sampling
2.1 Random number generation
2.2 Sampling from distributions
2.3 Variance reduction methods
3. Introduction to Output Analysis
3.1 Analysis of a single scenario – obtaining accurate results
3.2 Basics of comparing multiple scenarios
4. Experimental Design and Analysis
4.1 Time series analysis
4.2 Experimental design
4.3 Metamodelling
4.4 Simulation optimisation
4.5 Bootstrapping (for input data modelling as well)

COVERAGE OF WEB-BASED MATERIAL

AVAILABLE IN ADVANCE
Material intended for preliminary reading discussing basics of the statistical aspects of simulation.

SECURE YOUR PLACE TODAY