Making it Accessible: Applying the Optimisation Toolkit

At Biarri Optimisation one of our core priorities is to uncover interesting new mathematical problems in industry, build optimisation engines to solve them, and use those products to incubate new Biarri entities.  It is a constant source of amazement at how many disparate contexts that we can apply the tools of our trade: in particular, the tool of Mixed Integer Programming, which is one of the pillars of our discipline of Operations Research. Tools like this live in our optimisation toolkit.

Operations Research (OR) has its origins in World War II, where mathematics and analysis was used to determine what convoy size was most effective for avoiding German U-boat detection, the best paint colour to maximise camouflage for aircraft, and to identify the best trigger depth for aerial-delivered depth charges to maximise U-boat kills.  You can read more about these fascinating applications and more in the excellent book Blackett’s War.

The problems we solve

We tend to think of the problems that we try to solve in the following way.  First, we identify the decision variables that are involved: what elements of an operation do planners and users have the power to change?  Second, we establish the objective: what are planners looking to minimise or maximise?  This might be cost, or some combination of minimising cost with maximising benefits or safety (for example).  Lastly we pinpoint the constraints: what are the real-world limits on resources (people, equipment, budget) that have to be taken into account?

An example is a daily workforce planning problem faced by warehouse and distribution managers in many different industries.  Here there is a “profile” of required work across the day, of various types (e.g. forklift work, truck loading/unloading, racking replenishment, etc), and a set of personnel who have different skills and availabilities to do this work (permanent, casuals, with various possible start times).  How to cover all the work while keeping the total shift cost as low as possible?

The objective in this example is cost; the decision variables are the allowed shifts that can be operated; and the constraint is that all the work must be done by the appropriately skilled personnel.  The extra complexities we might encounter here come about where people can do multiple task types (e.g. they are qualified for both forklifts and manual truck loading), and there may be a changeover time incurred between tasks; they will also require meal and rest breaks, or incur overtime; there is fatigue to take into account (productivity typically starts dropping later in a shift); and equipment and space/congestion constraints.  You can even apply a productivity multiplier if different people are more or less productive at different tasks. Add to this the fact that some of the work can be done well ahead of time (pre-picking for truck loads, for example), which allows the work profile to be “smoothed” over, and you have quite a complex planning task indeed!

When we formulate this as a Mixed Integer Problem (MIP), we aim to solve it for the overall minimum cost.  This overall minimum cost is known as the global optimum, and it may be that, if you look at any one part of the solution in isolation, it might seem “sub-optimal”.  In our workforce planning example, for instance, a person might be allocated a very short shift. But this will make sense in the overall sense of the problem: it might be that there is a small piece of work left over that cannot “fit” into all the other shifts.

Feasible solutions

Part of the art of applying this type of mathematical approach lies in making sure that there is always an implementable solution.  For example, what if there are not enough people to cover the work? We do not want the solver to tell the user that the problem is simply “infeasible” – that there is no plan.  Instead, we build in extra decision variables which model the unallocated work over time, and we give these variables a high artificial cost in our objective (so the solver still tries to cover as much work as possible); now we can also report to the planner how much work is uncovered.

This technique is an example of a more general method which distinguishes between hard and soft constraints.  Hard constraints must always be met; there is no wiggle room.  By contrast, soft constraints (as in the “uncovered work” example) allow you to break a constraint, but incur some penalty for doing so.  In the workforce example, overtime can also be thought of as a soft constraint (once you exceed the regular shift limit, you incur extra cost).

Soft constraints can also be used as a way to “explore” the solutions that are near the optimal solution – there are some trade-offs you might be willing to make in order to save an extra chunk of cost.  You sometimes have to be quite careful when there are several types of soft constraint or extra penalties: for example, allowing very large penalties can obscure the smaller components of the objective. When you have multiple competing objectives, it can also sometimes be hard to explain why the result looks like it does.

Trusting the results

Of course, we must also exercise caution when trusting results of a mathematical process.  Our solvers will make arbitrary decisions when we do not provide guidance – a common instance is where there is a “shallow” cost function, which is where there are several similar solutions with the same or nearly the same cost.  These might be identical from an optimisation point of view: in our workforce context, an example is where several people with the same skills and availability might be able to do the same task: if it makes no difference to the total cost, who should we choose?  Often there is a real-world analog to this problem of “breaking ties”: here, for example, we might choose the employee based on seniority; or to ensure a longer term attractive roster; or a host of other factors.

Biarri has always strived to make optimisation “accessible” – part of which means making our optimisation results implementable in the real world – and in these examples I hope you have seen some of the nuances and complexities that underlie this promise as well as the tools that comprise our optimisation toolkit.

By Andrew Grenfell