Ruin and Recreate, Live
I started my Ph.D. in 2015 under Dr. Jingpeng Li, a kindly and intelligent man who was very patient with me going down the wrong roads and floundering over fairly fundamental and basic math. He had some interesting ideas on how to modify existing algorithms to improve their capabilities, and let me toy with them to begin to understand some of that fundamental math, as well as get a feel for how search algorithms, at their core, actually function.
Most search algorithms take a working solution, change one thing, and keep the change if it helped. That works until the solution is tangled, at which point every single change makes things worse and the search sits there, surrounded by improvements it cannot reach because each one requires three simultaneous moves.
Ruin and recreate knocks a hole in the solution and rebuilds the solution. This is the method behind a rostering paper I wrote in 2018[1] with colleagues at Stirling, York and BT, using a variant of Jingpeng's own algorithm: Evolutionary Ruin and Stochastic Recreate[2], where the wrecking ball is aimed by fitness rather than swung blindly. The demo below is that method on a simple roster. Part of the series on research, live.
Quick jargon guide
- Roster: who works which shift on which day. Here, twelve staff over fourteen days, each on an early, late, or night shift, or off.
- Fitness: one number saying how good a roster is, out of 100. Following the paper, hard constraints (covering demand, legal rest) are 95% of the score and soft ones (fair shares, no long runs) are the last 5%.
- Local search: repeatedly make a small change and keep it if the fitness rises.
- Local optimum: a solution where every small change makes things worse, which does not mean it is any good.
- Large neighbourhood search: the family this belongs to[3]. Instead of small changes, make one enormous change and repair the damage intelligently.
- Evolutionary ruin: the paper's twist. Every allocation gets its own fitness score, and the weaker an allocation, the more likely the ruin phase is to demolish it.
The demo
Each row is a person, each column a day. Cells are the shift they are working. The rows under the grid are the demand check: for each day and shift, how many staff over or under the requirement, so -2 on the night row means two short and +1 means one spare. A working cell carries the same figure when its shift is out of balance, which marks the allocations that are surplus and the ones holding up a short day. The panel under the stats scores each constraint separately: the two hard ones, which have to hold, and the two soft ones the last five per cent of the fitness is spent on.
One step is one full ruin and recreate, under the same simulated annealing control the paper uses. The ruined cells flash before they are refilled, so you can see the size and shape of the hole. The default strategy is the paper's: score every allocation, then demolish the probabilistically weakest. Switch to the blind strategies to see what the aiming is worth: scattered cells, a person's whole fortnight, or everybody's Tuesday.
| Constraint | Score | Status |
|---|---|---|
| Hard: demand covered on every shift | ||
| Hard: no night shift straight into an early | ||
| Soft: no run longer than five days | ||
| Soft: a fair share of the work (within one shift of the mean) | ||
| Fitness: 95 × hard + 5 × soft |
Fitness follows the paper's weighting: hard constraints (meeting each day's demand, no night shift straight into an early) are 95% of the score, soft ones (no runs longer than five days, a fair share of the work) are the rest. The acceptance is simulated annealing with the energy modelled as inverse fitness, the same control the paper uses, so early on the search sometimes keeps a worse roster on purpose.
Why breaking it on purpose works
A roster is full of constraints that interlock. Moving one person off Tuesday night leaves Tuesday night short, so the move is rejected, so the person stays. Every individual change is bad, and yet the roster as a whole is nowhere near as good as it could be. That is a local optimum with high walls (you try to climb them and only fall right back down, you need to jump out of there entirely).
Removing thirty assignments at once does not have to be an improvement, because the recreate step is not obliged to put them back where they were. It rebuilds greedily against the fitness function, which means it can discover an arrangement that no sequence of single moves would have reached, since each intermediate step in that sequence would have been rejected.
You can see this in action in the demo: small ruins converge smoothly and stall early. Large ruins jump around and take longer per step, since there is more to rebuild. The paper's answer is this: if you know which allocations are weak, a small, well-aimed ruin can do the work of a large blind one.
Aim the wrecking ball, or swing it harder
I measured all four strategies on this instance. The score is the median number of steps to first reach a fitness of 99.5, over five seeds, with a 200-step cap; "never" means the median run did not get there at all. Lower is faster:
| Ruin size | Scattered | Whole people | Whole days | Weakest (the paper) |
|---|---|---|---|---|
| 8 cells | 22 | never | 31 | 10 |
| 16 cells | 9 | never | 31 | 8 |
| 32 cells | 10 | 23 | 17 | 16 |
| 56 cells | 6 | 20 | 12 | 16 |
| 80 cells | 7 | 10 | 5 | 17 |
The fitness-guided ruin is fastest when the holes are small, eight or ten steps with a demolition of only eight cells, and gets no benefit from swinging harder, because it was never relying on volume in the first place. The blind strategies are the mirror image: they need size. Scattered cells come good from sixteen cells up; ruining everybody's Tuesday is the single fastest setting in the table at eighty cells, seven whole columns of the roster at a time.
Whole-people ruin at small sizes is the table's disaster zone, and the reason generalises. Eight or sixteen cells is one person's fortnight: freeing a single row while the other eleven stay fixed leaves the recreate step boxed in by everything it did not touch. Structured damage only pays when the structure being suspended is big enough to rearrange.
So the destroy operator and its size are not two parameters, they are one decision: aim, or swing big. The paper's selection operator decides, and its reward is reaching the same quality with a fraction of the demolition, which matters when every ruined cell costs rebuild time. Blind volume gets there too, eventually, by suspending so many constraints at once that the rebuild has room to rearrange everything.
What the demo is not
The real problem had a great deal more to it: engineers with different skills and a first-skill preference, shift rules dictating lengths, start-time windows and shift counts, alternating week patterns, UK working-time law, and two consecutive rest days per week as a soft target. The instances ran to around 200 employees, drawn from a domain of roughly 25,000 field engineers. The fitness function works with eight hard constraints and four soft ones, weighted 95 to 5.
What survives compression is the shape of the method, which is the part that transfers. Score it, break the weak parts, rebuild, and let the temperature decide what to keep.
Common questions
What makes it "evolutionary"?
The ruin phase runs on component fitness, in two mini-phases the paper calls selection and mutation. Selection scores every allocation and demolishes the probabilistically weakest, so bad genes die faster than good ones. Mutation then removes a few allocations at random, regardless of fitness, which keeps the search exploring even when every component looks healthy. Survival of the fittest, applied to the pieces of one schedule rather than to a population of schedules.
Is this just simulated annealing with extra steps?
SA is in there, but as the referee rather than the boxer. The engine is the ruin and rebuild; annealing referees, deciding whether the rebuilt roster replaces the current one, with energy modelled as inverse fitness, and its falling temperature is what stops the destruction of a nearly finished schedule late in the run.
Why greedy repair rather than an optimal one?
Because optimal repair of a thirty-cell hole is itself a hard problem, and you need to do it thousands of times. Greedy is fast, which buys iterations, and iterations buy quality. Where the repair can be made optimal cheaply, doing so is usually worth it: that variant is called large neighbourhood search with an optimal repair.
How big should the ruin be?
The amount of demolition emerges from the selection and mutation probabilities, which were tuned with a Taguchi design of experiments, and it falls naturally over the run: as the schedule improves, component fitness rises and protects good allocations from selection, while the falling temperature damps disruption late on. The table above shows why that self-regulation is the right instinct.
Does this beat a solver?
Not on a small clean instance. A solver hands you an answer with a proof attached, and this hands you an answer. The demo can announce a perfect roster only because the score in this toy stops at 100, so hitting the ceiling is the proof. Give it a real objective with no ceiling and the search has no way of knowing whether it is done. It wins when the instance is large, the constraints are awkward to express in a solver's language, and you need a good answer in seconds rather than a perfect one overnight. Most operational researchers care more about a good enough solution in time over a perfect solution a week late.
References
- Reid, K. N., Li, J., Veerapen, N., Swan, J., McCormick, A., Kern, M., & Owusu, G. (2018). Shift Scheduling and Employee Rostering: An Evolutionary Ruin & Stochastic Recreate Solution. In 2018 10th Computer Science and Electronic Engineering (CEEC), 19–23. IEEE. Google Scholar
- Li, J., Bai, R., Shen, Y., & Qu, R. (2015). Search with evolutionary ruin and stochastic rebuild: A theoretic framework and a case study on exam timetabling. European Journal of Operational Research, 242(3), 798–806.
- Schrimpf, G., Schneider, J., Stamm-Wilbrandt, H., & Dueck, G. (2000). Record Breaking Optimization Results Using the Ruin and Recreate Principle. Journal of Computational Physics, 159(2), 139–171. https://doi.org/10.1006/jcph.1999.6413
