{"body":"

Leveraging our optimisation expertise

Our team has plenty of experience solving optimisation problems. In the past, we’ve worked on challenges such as optimising customer order delivery routes and automating staff rostering - taking account of multiple constraints.

Broadly speaking, optimisation is a task of finding the best solution to a problem from a set of possible solutions with respect to some criteria.

In our case, we consider combinatorial optimisation problems where the problems are discrete and the set of possible solutions is finite.

However, the size of the set of possible solutions is typically so big that exhaustive enumeration over all of them to find the optimal one would be computationally intractable. Therefore solving such problems typically requires the use of advanced algorithms.

Our team employs a wide-ranging toolkit of optimisation methods, which involves both heuristic and exact approaches.

Examples of the former include: local search methods, genetic algorithms and metaheuristics. Exact methods include, as an example; linear and mixed integer programming, as well as constraint programming.

Making it work with constraint programming

Constraint programming is one of the most efficient approaches for solving scheduling problems.

It’s a paradigm that consists of two parts: problem modelling as a constraint optimisation problem, and solving of the model by a constraint solver.

Constraint modelling involves representing the problem in question in terms of variables, each of which can take values from certain domains as well as constraints, which are relations between those variables. A constraint optimisation model also defines an objective function, which describes the criterion we want to optimise, and the optimisation goal (minimise or maximise).

A feasible solution to a constraint optimisation problem is an assignment of values to variables so that each variable is assigned a value from its domain, and all the constraints are satisfied. An optimal solution is a feasible solution that has the best objective function value over all the feasible solutions.

For example, we could define a model having two variables, X taking values from the domain {1,2,3} and Y taking values from the domain {4,5,6} and a constraint Y−X ≥ 4, with the objective being to maximise X+Y. An optimal solution to such a problem would be an assignment X=2, Y=6.

The solving part of constraint programming can be done by an off-the-shelf solver, with a number of open access and commercial solvers available in the market.

However, building an efficient constraint model for a solver to solve is the key to successfully applying the technology.

Building upon our prior experience in this domain, we were able to create an efficient constraint model taking full advantage of so-called global constraints.

These global constraints are associated with specialised algorithms implemented inside the solver that allow the solver to efficiently prune the solution space, based on a specific global structure of the relation between the affected variables.

This in turn allows the solver to produce solutions faster and can ultimately determine whether the solver is capable of generating a solution within reasonable computation time.

Teamwork made the impossible, possible

The task involved a significant implementation effort and collaboration between the Data Science team and the Business Planning team.

While we were working on the algorithmic solution and its implementation, the Business Planning team was analysing and adjusting the requirements, creating test cases and evaluating the test schedules generated by the algorithms.

Working together, we were able to cover all stages of the project from collection of requirements through to deployment in under two weeks.

As our team had experience in applying constraint programming, and worked with good design practices, we were able to reuse parts of existing code to save time.

The resulting tool enabled us to automatically produce weekly testing schedules for around 3,500 employees across 4 sites.

Our team is proud to have played a part in developing an efficient testing programme, which contributes to keeping the team safe in these unprecedented times.

","presentation":{"classes":"","theme":"theme-default","columns":""}}

The role of operational research at Ocado Technology during COVID-19