Category Archives: Optimization

What is Operations Research (OR)?

This post was originally posted on a University of Nottingham blog.


What is Operations Research (OR)?

The terms Operations Research (American term) and Operational Research (European term) are used interchangeably. The discipline is also referred to as:

  • Management Science (most often used in a Business Management sense)
  • Decision Science (less frequently used, but is used most often when statistics are involved)
  • Analytics (a relatively new term but is increasingly used)

Operations Research has close links with Mathematics and Computer Science. It draws on many areas to solve the various problems that it is presented with. Included in these are

  • Optimization (drawing on mathematical programming and and areas such as Linear Programming)
  • Modelling
  • Simulation
  • Heuristics
  • Meta-heuristics
  • Hyper-heuristics
  • Evolutionary Computation
  • Game Theory
  • Statistics

 

A Traveling Salesman Problem solution for USA (Figure credit: David Applegate, Robert Bixby, Vasek Chvatal and William Cook)
A Traveling Salesman Problem solution for USA (Figure credit: David Applegate, Robert Bixby, Vasek Chvatal and William Cook)

The essence of Operations Research is to provide (ideally) optimal, or near optimal solutions to complex decision problems. Probably, the most well known problem (at least in the scientific arena) is the Traveling Salesman Problem (TSP) which can be described as follows:

A salesman has to visit a number of cities. He can choose which one he starts at, but he must complete his tour at the same city. He must visit every other city exactly once. The aim is to minimize the distance traveled.

Whilst being very easy to describe, the TSP gets very difficult to solve (at least in polynomial time) due to the fact that the number of possible tours grows exponentially with the number of cities (the actual number of tours is n!/2 (we divide by two as a tour in one direction is the same as a tour in the opposite direction)).

Historical Details

Like many things, especially in Computer Science, many of its origins can be traced back to the second world war, necessity being the mother of invention, although some would argue that OR’s roots can be traced back beyond this point. Given the subject, you’d expect that many people would have documented the history of the subject and, indeed, this is the case. I have provided below some sources which the interested reader might want to follow.

  • [1] Gass S.I. and Assad A.A. An Annotated Timeline of Operations Research: An Informal History, Springer. ISBN-10: 1402081162, ISBN-13: 978-1402081163
  • [2] Historical Origins of Operations Research, http://en.wikipedia.org/wiki/Operations_research#Historical_origins, last accessed 2nd Mar 2013
  • [3] Gass, S. I., A.A. Assad. History of operations research. J. Geunes, ed. INFORMS TutORials in Operations Research, Vol. 8. INFORMS, Hanover, MD, pp. 1–14

Why is OR so hard?

The type of combinatorial explosion we see in problems such as the TSP often underpins the problems that we face in OR. In fact, the problems where is is easy to verify (i.e. in polynomial time) if a solution is correct but to find the optimal solution cannot be done (we suspect) in polynomial time is often at the heart of the problems we are trying to solve in OR.

These problems are NP-Complete (in fact NP-Hard, in the way we are presenting the TSP as it is an opimization problem – but we can easily convert it to an NP-Complete problem by framing it as a decision proble (e.g. “is there a route that is less than n length?”)). That is, we can easily verify a solution is correct (given a TSP solution, we can easily add up the distances to verify that the solution we have been given is correct) but we do not know of a polynomial time algorithm that is guaranteed to return an optimal solution. Indeed, proving P=NP (or not) is one of the Millenium Problems and if you are able to do it, you will receive a prize of $1M USD.

There are some common problems that you will often come across in OR. We have already mentioned the TSP.

The Vehicle Routing Problem!
The Vehicle Routing Problem!

The Vehicle Routing Problem (VRP) is another classic OR problem. As the name suggests, this problem is about scheduling deliveries for vehicles. The classic version is the Capacitated Vehicle Routing Problem (where we minimize total distance traveled, but have to respect vehicle capacities) but there are many variants, such as VRPTW (Vehicle Routing with Time Windows), where deliveries have to be made at certain times. In fact, VRP and TSP are very closely related.

Another classic problem is graph coloring. That is, given a graph with various connections between the nodes you have to try and color the nodes, using as few colors as possible, such that no nodes which are connected have the same color. This problem has an obvious application is coloring maps but you might be surprised to know that it underpins many (many, many) other problems. As an example, university examination timetabling (i.e. scheduling the exams for our students) can be modeled (and solved) as a graph coloring problem. There are almost an infinite number of problems that can be modeled as a graph coloring problem.

Second to the TSP (and this is debatable, it might be first), with respect to the number of papers written, machine/job shop scheduling problem. This problem, in its simplest form, looks at scheduling factories.

Given a number of machines, and a number of processes that have to be gone through to produce a product, what is the best way to utilize the machine(s) to maximize the throughput?

Graph Colouring Problem
Graph Colouring Problem

Like the graph coloring problem, Job Shop Scheduling (JSP) and Flow Shop Scheduling (FSP) can be used to represent many other problems, that are about as far away from the factory floor as you can imagine (how about having telescope(s) in space and trying to schedule their usage for various scientists).

Methodologies

If we could prove that P=NP (which most people think unlikely) then we would be able to find the optimal solution to many of the important problems in OR. That is, we would have a polynomial time algorithm that would give us an optimal solution in a reasonable time. Of course, it might still take a long time but this better than an exponential time algorithm that might take millions of years to return the optimal solution, even on the fastest computers. In fact, there are many problems (or many problems of sufficient size) where we would have only considered a small number of the possible solutions even if we started the algorithm when the dinosaurs were roaming the earth.

However, there are sophisticated algorithms (such as linear programming) that are increasingly able to solve moderately sized problems to optimality.

When these fail (or we find it difficult to model the problem in sufficient detail to use a mathematical programming approach) we tend to use either heuristics, meta-heuristics, hyper-heuristics or evolutionary computation.

The definition of these is not formal (in that, we could argue where they blur at the edges) but:

  • Heuristics tend to be one pass algorithms and are quite quick.
  • Meta-heuristics are based on phenomena seen in the real world. Things like tabu search (based on memory) and simulated annealing (based on the way we cool metal).
  • Hyper-heuristics are a development of meta-heuristics (although their roots, strangely, can be traced back to before the term meta-heuristics was coined). They are based on the idea of exploring the heuristic space, rather than searching the solution space directly.
  • Evolutionary Computation are algorithms that are based on Darwin’s principles of natural evolution (survival of the fittest) where we have a population of solutions which compete against each other for survival. Common algorithms in this domain include genetic algorithms, genetic programming, honey-bee mating algorithms and particle swam optimisation.

 

Where do we publish?

If you are looking for journals that you might want to consider publishing in then Thomas Reuters, Web of Knowledge, Journal Citation Reports has a specific category for Operations Research & Management Science. For the 2011 journal rankings, this category contained 77 journals. Of course, not all of them will be suitable for a given piece of research but these 77 journals all most (if not all) areas of Operations Research.

 

Want to know more?

There are too many resources to list here, and a serch on a bibliographic search engine such as Science Direct is likley to throw up more references than you would imagine.

But, youtube has a god set of videos where you can Learn About OR.

A couple of videos that caught my eye are OR in Sport and OR in Transport

 

About the author

Graham Kendall is a Professor of Computer Science who works in the Automated Scheduling, Optimisation and Planning Research Group (ASAP). He is a Fellow of the OR Society, as well as an Associate Editor of the Journal of Operational Research Society (in addition to several other journals). He has published widely in Operations Research, as well as other areas. His publications can be seen here.

He has over 30 years experience in OR, both in industry and academia.

Graham is currently based on the University of Nottingham’s Malaysia Campus (UNMC) where he is the Vice-Provost of Research and Knowledge Transfer.

Contact details:

 

References

[1] Gass S.I. and Assad A.A. (Author) An Annotated Timeline of Operations Research: An Informal History, Springer. ISBN-10: 1402081162, ISBN-13: 978-1402081163

[2] Historical Origins of Operations Research, http://en.wikipedia.org/wiki/Operations_research#Historical_origins, last accessed 2nd Mar 2013

[3] Gass, S. I., A.A. Assad. History of operations research. J. Geunes, ed. INFORMS TutORials in Operations Research, Vol. 8. INFORMS, Hanover, MD, pp. 1–14

 

Optimising the future with mathematics

Geoff Prince, Australian Mathematical Sciences Institute

AUSTRALIA 2025: How will science address the challenges of the future? In collaboration with Australia’s chief scientist Ian Chubb, we’re asking how each science discipline will contribute to Australia now and in the future. Written by luminaries and accompanied by two expert commentaries to ensure a broader perspective, these articles run fortnightly and focus on each of the major scientific areas. Today, we add mathematics to the mix.

Mathematics is an absolutely critical part of our future – and we can maximise its impact for the public and private good over the next 11 years if we take the opportunity now.

It is the multidisciplinary and universal nature of mathematics which makes this true: multidisciplinary because of its vast scope and universal because of the effectiveness of its processes.

In some fields it plays a supportive role and in others, the lead. I will describe a lead role which will be crucial to achieving the sort of economy we want: the optimisation of public and private sector enterprise. (I will touch on statistics and its role in data analysis only in passing as my esteemed colleague Terry Speed will cover it later in this series.)

Charles Darwin summed up the deep importance of mathematics when he said

Mathematics seems to endow one with something like a new sense.

Mathematicians do not have a monopoly on this extra sense. Broad mathematical capability across the community underpins most qualities identified in the aspiration for 2025. Bankers, nurses and engineers competently practise various forms of mathematics on a daily basis.

Today’s 12-year-olds entering secondary school will be 2025’s young graduates.
After the slide in the performance of our 15-year-olds exposed in the latest Programme for International Student Assessments (PISA) results, it’s not clear that they will enjoy the same broad mathematical capability as today’s 23-year-olds.

The Australian Mathematical Sciences Institute’s (AMSI) own aspiration for 2025 is to lift the percentage of secondary maths classes taught by qualified maths teachers from an appalling 66% now to 100%.

We have serious work to do here just to maintain the status quo, but we must also be prepared to deal with the new quantitative and qualitative challenges thrown up by this rapidly changing world – and to do that, we must be more agile than we are at present.

Getting practical about mathematics

Biology is a case in point. The slow uptake of mathematics and statistics in the university biology curriculum hampers our progress despite the demand for mathematically capable specialists at the research frontier.

The lesson here is to connect mathematics and biology in our schools, two disciplines which have not traditionally been close (notwithstanding Darwin’s observation). Maths is meeting the biosciences in the 21st century much as maths met physics in the 20th, and we must communicate this through the curriculum – not leave it to Brian Cox, Simon Singh, Facebook and Twitter.

We need our ‘mathematical sense’ or we risk ending up with The Blind Leading the Blind (Pieter Bruegel the Elder, 1568).
Wikimedia Commons, CC BY

The advanced mathematics that the discipline itself practises loosely splits into

  1. theoretical mathematics: developed without an immediate view to external application. It is the deep intellectual nature of theoretical mathematics which attracts many to the discipline (think of the Clay Millennium problems).
  2. applicable mathematics: focused on practical benefit on various time scales. It is applicable mathematics which most directly, but not exclusively, impacts on our aspirations for 2025.

Many of any of us move freely between the two and history shows that the multidisciplinary capacity of mathematics depends critically on the health of the discipline proper. The use of 19th and 20th century differential geometry in 21st century computer graphics is a striking example. This pointed observation is aimed at the managements of our universities!

The word cloud below shows some public, private and research enterprises, all contributing critically to where we will be in 2025 and all employing or engaging with research-trained mathematicians and statisticians.

Wordle

Mathematicians’ roles are increasingly important in a world addicted to progress, and they are multidisciplinary in nature – statisticians work with retailers to refine and analyse their loyalty programs and mathematicians work with banks to manage financial risk and with the hospitals to manage emergency ward workflows.

We make a fundamental contribution to the growth of knowledge based industries and to the smart operation of the natural and primary resource sectors. Unfortunately we don’t communicate this very well, especially to students and their parents, but we are making a start.

The practice of this applicable mathematics can be broken into support roles and lead roles. Roughly speaking the support roles involve the practice of existing sophisticated mathematics and the lead roles involve active research:

  • computational mathematics plays a lead role in industrial, biological, economic and environmental modelling, such as in the increasing accuracy and sophistication of climate change models
  • bioinformatics plays a lead role in genetics, creating algorithms to analyse genomic data to expose genetic markers for disease
  • optimisation should play a lead role in both making the Australian economy competitive in 2025 and in improving our national well-being.

Optimising optimisation

Broadly speaking, the mathematical field of optimisation involves determining an optimal scenario (relative to some criteria) among a collection of alternatives.

The determination of the most efficient route between two locations, where “route” and “location” can have many meanings, or the most economical use of resources in production processes. Optimisation problems can involve thousands of variables and minimise or maximise many “objective functions”.

It sounds dry, but it cries out “productivity growth!” and “competitive advantage!” and, in times of emergency, “lives saved!

Darwin would certainly agree that optimisation is in his “new sense” category.

Australia is getting better at optimisation, from traffic management to mining to aircraft scheduling, but it’s patchy. The defence forces are very good at it, in part due to the work of the Defence Science and Technology Organisation (DSTO), as well as the CSIRO, NICTA, IBM and some of the universities.

Adrianne Behning Photography/Flickr, CC BY-NC-ND

The health sector is not uniformly good at optimisation, nor are our public transport systems.

Small to medium enterprise is not good at it at all. We are babes in the woods compared to countries such as Germany and the US for whom optimisation is worth billions.

The really smart way to optimise infrastructure is to build optimality into the design. We almost never to do this – we usually optimise as an afterthought, if at all.

But one shining Australian example of optimisation in design is the work of business analytics and optimisation company Biarri Commercial Mathematics on the National Broadband Network (NBN) – work so good that they are one of six global 2014 finalists for the prestigious Franz Edelman Prize.

The mandating by government of optimisation integral to design for significant public and private infrastructure projects would have a transformative impact on the Australian economy. It would not only boost productivity but build in competitive advantage and contribute to a sustainable future.

Optimisation would become part of the economic culture at all scales.

By keeping the bureaucracy to a minimum this measure would encourage the growth of dynamic companies like Biarri and draw on the capacity of CSIRO, IBM, NICTA and the universities, all of whom would be able to tender for the design work.

It would strengthen the mathematical sciences and thrust us, sure-footed, towards 2025 and beyond without fear of falling into the ditch of mathematical ignorance.


Nalini Joshi, Professor of Mathematics at the University of Sydney

Mathematics is a universal language that unlocks innovation by abstracting a problem to reveal patterns that answer the crucial questions. The key to Australia’s future competitiveness and security lies in continually creating and adapting mathematical representations of the real world.

Mathematical truths make a complex world more comprehensible and manageable; they are intertwined with efficiency and innovation at all levels of the economy.

lytfyre/Flickr, CC BY-NC-SA

Mathematics can show us how to minimise traffic snarls in our cities, cut costs in a complex network of rail transportation, avoid congestion on the internet, produce innovative designs in optical lenses, weigh costs and benefits of environmental policies and optimise a small business plan.

Mathematics can create new and better Australian industries. It is now central to fundamental questions of nature, life and health.

How does genomic information lead to development and better health in early life? How can the resolution of medical images be improved while reducing their file size? How can mathematics be used to create a safer regulatory framework for financial markets?

The more technologically sophisticated a society becomes, the more critical its need for mathematical thinking. The pathways towards economic diversity and opportunity are paved with mathematics.


John Rice, Honorary Professor of Mathematics at the University of Sydney

A smart economy depends on mathematical skills but you would hardly know it. Mathematics in practice is often not recognised as such, and unrecognisable in terms of school and undergraduate mathematics. This is the great failure of mathematics education.

The greatest contribution that the discipline of mathematics could make to Australia’s smart economy is to remedy that.

The remedy concerns approach as well as content. Mathematics as it is practised, in research and professional occupations, requires thought, creativity, judgement, questioning and problem solving. An economy based on production lines might not require these skills as a matter of course, but a knowledge and innovations-based economy does.

queensu/Flickr, CC BY-NC-ND

Current mathematics education, in schools and universities, is satisfied with programming students to carry out certain mathematical processes, and assessment rewards students who can calculate everything even if they understand nothing.

It’s more like preparing for a production line than a knowledge based economy.

The mathematics discipline seeks a remedy in improving the knowledge base of those teaching mathematics. However, “upskilling” teachers with “more of the same” will not deliver mathematics in the form that a smart Australia needs.

We need mathematics “to be taught more like it is done” by those engaged in it, in both the innovations economy and research. This is a cultural change that involves the discipline itself, one that must be mainstreamed into school and university systems.

Without this, the connection between mathematics and the economy will remain dubious in the public mind, and mathematics will remain hamstrung in achieving its proper influence and delivering its benefits to a 21st century Australia.


This article is part of the Australia 2025: smart science series, co-published with the Office of the Chief Scientist.
Further reading:
Australia’s future depends on a strong science focus today
Physics: a fundamental force for future security
Proteins to plastics: chemistry as a dynamic discipline
Australia can nurture growth and prosperity through biology
A healthy future? Let’s put medical science under the microscope
Groundbreaking earth sciences for a smart – and lucky – country
To reach for the stars, Australia must focus on astronomy
Marine science: challenges for a growing ‘blue economy’
Building the nation will be impossible without engineers
Australia’s got ICT talent – so how do we make the most of it?
Agriculture in Australia: growing more than our farming future

Geoff Prince, Director and Professor, Australian Mathematical Sciences Institute

This article was originally published on The Conversation. Read the original article.