Client Login
Operations Research (Management Science)
Operations Research (OR) isn't really research, it is a science (sometimes called Management Science). To clarify: Double-Digit Numerics does research in the science of Operations Research. It has some other strange terms. It uses "programming" to refer to optimisation, not computer programming.
Operations Research is the science of applied optimisation. It seeks to optimise some management-related concept such as profit maximisation, time minimisation, resource allocation, scheduling, logistics, etc. It originated in the second world war where it was used to optimise military operations. A famous example of its use was to find the optimal convoy size to reduce ship losses. It was found that large convoys were better than small.
Operations Research provides many of the tools used in financial optimisation such as portfolio optimisation. The list below is written from the tools perspective rather than from the application perspective. Typically an application would use more than one tool anyway. The general approach is to formulate a model for the operations to be optimised then use the tools below to optimise that model.
Since the war OR has had a major impact on the efficiency of business operations worldwide. An investment in OR can easily pay for itself many times over.
Linear Programming
Linear programming has been ranked among the most important scientific advances of the mid-20th century. Today it is a standard tool that has saved many billions of dollars worldwide.
It refers to the optimisation of a linear objective function, subject to linear equality and inequality constraints. A linear function is one that can be expressed as a1*x1 + a2*x2 + ... an*xn. A linear constraint is where a linear function is constrained to have values in a certain range.
An (oversimplified) example: the profit from selling butter is a1 per kilogram and from cheese is a2 per kilogram. Let x1 be the number of kilograms of butter produced and x2 the kilograms of cheese. You have to choose how much butter and cheese to make from z kilograms of milk and so your constraints are that x1 < z and x2 < z. Very simple example that you could optimise in your head but real life examples can have hundreds of variables and constraints.
In fact, Linear Programming has many applications that do not seem to be Linear Programming problems at all - see the Transportation Problems and Network Optimisation sections below.
Nonlinear Programming
This is similar to Linear Programming but the objective function and the constraints don't have to be linear.
An example from Portfolio Optimisation is where you want to minimise the variance of a portfolio. The variance is a quadratic function (it uses squared terms) of the stock holdings. So this is a Quadratic Optimisation problem.
In general, Nonlinear Programming is harder to do than linear. So it requires more computer time. Often so much more that you cannot get the exact optimum solution so have to settle for close-enough. Heuristics and short-cuts are the norm. Double-Digit Numerics has plenty of experience with heuristics and simplifying assumptions. Our motto is "near enough is good enough." There is plenty of scope for doing research in this area to improve algorithms and thereby gaining an edge over your competitors.
Dynamic Programming
Dynamic Programming is used to make a sequence of decisions over time. An example that we have developed code for is America's Cup yacht racing where you have to sail an optimal route through a wind field. Yacht racing is a fascinating area where a straight line is not the fastest way to your destination. And also where it may be faster to take a detour off course to exploit a patch of extra strong wind off to the side. An application in Portfolio Optimisation is optimisation over more than one time frame.
The advantage of the method is that short term decisions may not give the best long term route. Sailing into the strongest patch of wind may not get you to the distant mark faster than using a less strong patch of wind.
The essence of the method is to work backwards from the destination. Divide the path into discrete units. Find the best route from the last unit to the destination. Then make that unit the next destination, and repeat the process. If the process you are dealing with has some randomness in it then use expectations instead of raw numbers.
It is quite a fascinating optimisation and it is one of DDNUM's favourites.
Combinatorial Optimisation
The classic Combinatorial Optimisation problem is the Traveling Salesman problem. You have to visit 30 cities (or you have 30 packages to deliver) - what is the fastest route to take? It is called a Combinatorial problem because the number of possible different routes rises "combinatorially" as the number of cities increases. Combinatorial growth is faster than arithmetic growth or exponential growth and so the problem quickly becomes too difficult to solve by trying all possible routes.
For example: for 5 cities there are 120 routes. For 10 cities there are 3628800. And for 30 cities there are 265252859812191058636308480000000. Since it is quite feasible for a courier to deliver 30 packages in a day real life problems can easily be too difficult by trying all possibilities.
In fact there is no known method for this problem and there is a million dollar prize for anyone who can solve it. But in real life near-enough is good-enough and there are some good methods for getting an approximate answer. In fact some methods are so good that the approximation usually gives the exact optimum for even several thousand cities.
Combinatorial Optimisation problems occur in finance - an example is taking the best 50 stocks out of 8000 (which can be done in 4x10^130 different ways). Approximation methods using heuristics can be used here to get close enough to the optimum. We have a liking for methods using Genetic Algorithms for solving that one. These algorithms mimic evolution to produce better and better solutions at each step of the optimisation.
Transportation Problems
How do you transport goods and how do you assign people to tasks? These important problems have the name Transportation Problems and are special cases of Linear Programming. Because they are special cases special techniques can be used to solve them more efficiently.
The transportation problem can be massive. For example Fonterra New Zealand has to, twice a day, visit thousands of farms with hundreds of milk tankers and deliver milk to dozens of milk collection points. They have been working on this optimisation problem for at least three decades. They make so many trips by truck that they now use GPS to measure how much travel they do off public roads and on private farm tracks so that they can claim back road user charge rebates. The rebates are minute for each trip but they add up to worthwhile amounts over all trips.
The Assignment Problem is where you have n employees and n tasks and a cost for each employee to do each task. You want to make the assignment to minimise the total cost. This turns out to mathematically be a Transport Problem.
Network Optimisation
Networks such as transportation, communication, and electrical usually have capacity constraints and costs associated with their use. This gives rise to problems such as the Minimum Cost Flow problem, the Shortest Path problem, and the Minimum Spanning Tree problem.
There are ways of reducing these problems to special cases of Linear Programming problems and specialised methods for solving them.
Game Theory
Stock markets are competitive markets and one person's gain can be another person's loss. Game theory deals with competitive situations.
Again it turns out that Linear Programming is useful for optimising certain simplified games. But real-life competition is usually too complicated for these methods and so this area is a hot area for research. Noone is yet close to finding the optimal game-theoretic solution to America's Cup yacht racing.
Queuing Theory
Queues are a part of everyday life and waiting in a queue is an easily-measured waste of time. Queuing theory develops models to represent queues and allows optimising for minimising the costs of waiting and the costs of providing service. Since queuing has random elements to it (people arrive at a queue at random) this type of modeling requires stochastic optimisation. This means minimising expected waiting time rather than actual waiting time. It uses probability distributions and uses more statistics than the methods above.
Some of this queuing theory is useful in modeling market trading so as to minimise costs of trading.
Simulation
Simulation is one of the most widely use Operations Research techniques because it is a powerful, flexible, and intuitive tool. It is particularly useful for stochastic systems (those with randomness). It does not refer exclusively to computer simulations. Testing model yachts in a wind tunnel is a simulation of the full-sized yacht.
The essence of OR simulation is to imitate on a computer the behaviour of the system that you are studying. Then you can apply what you learn from the simulation to the real-world system. A simulation is usually different from a quantitative model of the system. The model attempts to imitate the system without the probabilistic noise in the system whereas a simulation would replicate the noise as well. The former could be used for predicting the future state of the system, the second for estimating the accuracy of that prediction.
There is more on Simulation in the Computing section.