A Basic Guide to Optimisation

Often problems occur where we want to maximise or minimise some quantity. This is pretty easy to do for simple functions or graphs that we can plot. When the information is plotted in a graph we can visually look for the point in the graph which is highest or lowest. Alternatively if we have a function that can be written mathematically we can use differentiation to find its maximum or minimum.

What optimisation is able to cope with is finding the maximum or minimum of a quantity given that it is limited or `constrained’ by some other facts. Think of trying to build as many products in a factory as you can, whilst only having a limited amount of raw materials and workers both of which need to be used to build the product.

Maximisation or Minimisation?

Normally we want to deal with either a maximisation or minimisation problem. It turns out that these two problems are in fact two sides of the same coin: finding the minimum of some function $f(x)$ is the same as finding the maximum of $-f(x)$. As a result we typically define optimisation problems in the form of a minimisation problem.

$\min f(x) = \max -f(x)$

Source: ltcconline

Advertisements

Maintenance and Optimal Stopping

Imagine we have a machine in a factory that makes products which are sold to the general public. Ideally we want to make as many products as possible so we can sell them all to make a nice healthy profit. This means that we really want to be running the machine all through the day with no unnecessary stoppages.

Realistically however we know that machines do in fact breakdown and companies employ teams of people whose job it is to maintain the machines so that they can keep them running or repair them if they do break. Generally these maintenance teams will have a planned schedule of times when they will stop the machine in order to do their necessary checks and servicing.

This approach works well except for the fact that there are often conflicting views between the maintenance department and the production department. The production department wants to make sure that products are always being made (as few stops as possible), whereas the maintenance viewpoint is that the aim should be to stop the machine breaking down (needing a lot of stops). This poses the question of how to find the optimum balance between having a reliable machine and a productive machine?

Optimisation in Car-Sharing Systems

For many people the costs of owning, running and maintaining a car are simply too big to justify having one. Having to pay hundreds, if not thousands of pounds to cover insurance, road tax and fuel costs for only a few short journeys a week to work or to the shops doesn’t make financial sense. One alternative to this that has proven popular is ‘car-sharing‘ or ‘car-clubs‘. These schemes allow members to access vehicles owned by the company by reserving them in advance so they can use them for the short trips they might make in a day. This could be anything from picking up the kids from school, popping down to the shops or going out for a few hours at the weekend.

There are several other benefits to using a car-sharing schemes in addition to any potential financial savings. By using a single vehicle to do several different people’s short trips means that less cars are on the road in total reducing traffic congestion and vehicle emissions. Even something as simple as being able to guarantee a parking space when you reach your destination can be attractive, particularly in busy inner cities.

Optimal Search Problems

One active area of research within STOR-i is the problem of how to optimally search for something or someone. This is a problem of practical importance with it being used for many real world applications. Bomb disposal squads need to search for unexploded ordinance, search parties want to look for survivors of disasters and the police want to find people on the run from the law.

Like most things the best way to build intuition to a problem is to start by constructing smaller toy models of the system. We can represent the places where an object might be hidden as arcs in a network which are connected to each other with nodes. This type of structure is deliberately similar to that of a road system, the arcs represent streets and the nodes are the street corners. The object that we want to find will be hidden along one of the streets and the job of those searching is to find it as quickly as possible.

Example Network for Optimal Searches

Emergency Planning with OR

One recent talk that stood out to me was given by Marc Goerigk and talked about how operational research can be used to help improve evacuation planning for emergencies. For example unexploded WWII era bombs, Lancaster floods or terrorist incidents.

The ideas I will talk about are to do with using an optimisation approach to give a good lower bound on the evacuation time. Simulation techniques on the other hand are more useful for finding an upper bound on the evacuation time.

A clever thing to do when we are trying to model real world places is to try and represent the place in a network. Essentially we can take a map and represent it in a graph network using nodes and arcs. Arcs generally represent paths or roads and nodes the intersection of these paths and roads. This allows us to simplify tricky features such as curved roads into nice straight lines.

Transforming a map of my flat into a network diagram