The Great Deluge Algorithm

Picture a golfer standing on a hilly landscape — the height of the terrain is the quality of a solution to some hard problem. The golfer wants to reach the highest peak, but they can only take steps to neighboring spots. The trap: many hills have local peaks that are not the global best. A climber who only ever steps upward gets stuck there.

Simulated annealing escapes by occasionally accepting a downhill step, with a probability that shrinks over time — mimicking how a metal cools and its atoms settle. The idea works, but the temperature schedule and the acceptance probability add complexity that can be tricky to tune.

In 1993, the physicist Günter Dueck published a strikingly simpler idea: instead of a cooling temperature, imagine the landscape flooding with water. The water level rises steadily from the starting quality. You may move to any neighboring solution — as long as it stays above the waterline. As the flood rises, solutions below the current level become forbidden; the search is squeezed upward until only high-quality solutions remain reachable.

No probability. No temperature schedule. Just a rising threshold and the rule: stay above the water.

The algorithm was named the Great Deluge (after the biblical flood) and published alongside a companion heuristic called Record-to-Record Travel in the journal Journal of Computational Physics. Both have since found a home in scheduling, timetabling, and combinatorial optimization.

Below is a one-dimensional landscape. The dot is the current solution; the blue fill is the rising water. At each step the algorithm tries a random neighbor and accepts it only if it stays above the waterline. Watch as the flood closes off lower valleys and forces the dot upward.

<!-- {{c_container_comment}} -->
<div class="controls">
  <label>{{label_rain_rate}} <span id="rain-val">3</span>%
    <input type="range" id="rain-slider" min="1" max="10" value="3" step="1">
  </label>
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<canvas id="cv" width="560" height="230"></canvas>
<div class="status" id="status">{{status_ready}}</div>

/* {{c_reset_comment}} */
* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #222; background: transparent; }
.controls { display: flex; gap: .6rem; flex-wrap: wrap; align-items: center; margin-bottom: .6rem; }
label { font-size: .85rem; display: flex; align-items: center; gap: .4rem; white-space: nowrap; }
input[type=range] { width: 80px; accent-color: #1d3557; }
button { font: 600 13px system-ui; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
canvas { display: block; width: 100%; max-width: 560px; border-radius: 8px;
         background: #f4f7fa; border: 1px solid #cdd9e3; }
/* {{c_status_comment}} */
.status { font-size: .9rem; font-weight: 600; margin-top: .5rem; min-height: 1.4em; }
.status.running { color: #1d63b0; }
.status.done { color: #0a7d33; }
.status.stuck { color: #c92f3c; }

// Code not found

Drag the Rain Rate slider to control how fast the water rises. A slow rain gives the search more time to explore; a fast rain rushes the dot to higher ground before it has mapped the terrain. The best setting depends on the landscape — tuning the rain rate is the main practical knob on the Great Deluge.

The Great Deluge is a metaheuristic — a strategy for searching large solution spaces that offers no polynomial-time guarantee on hard problems.

• Each step is cheap. Evaluating a neighbor and comparing it to the water level costs the same as one quality evaluation — $O(1)$ extra work per move.
• No guarantee of optimality. For NP-hard problems like scheduling or graph coloring, no efficient algorithm is known to always find the global optimum, and the Great Deluge is no exception.
• Deterministic acceptance. Unlike simulated annealing, the Great Deluge never accepts a worse solution. It only accepts neighbors that are at least as good as the current water level. This makes behavior easier to reason about — and sometimes easier to tune.
• Rain rate is everything. If the water rises too fast the search locks in prematurely; too slow and it wastes time exploring swamped terrain. In practice, the rain rate is set as a fraction of the initial quality range: $\text{rain} = \alpha \cdot (q_{\max} - q_{\min})$ per step, where $\alpha$ is typically between $10^{-5}$ and $10^{-3}$.
• Variants extend the idea. The flex-deluge resets the water if progress stalls; the star-deluge adjusts the rate dynamically. Each trades simplicity for robustness.

The practical payoff is that the Great Deluge is often faster to implement and tune than simulated annealing, and on many benchmark problems it finds solutions of comparable or better quality.

The Great Deluge's combination of simplicity and effectiveness has made it a practical choice wherever combinatorial search is needed:

• University timetabling: assigning lectures, rooms and timeslots so no student has a clash is a classic NP-hard problem. The Great Deluge consistently ranks among the top metaheuristics in the International Timetabling Competition benchmarks.
• Nurse and staff scheduling: hospital rosters must satisfy dozens of hard constraints (shift lengths, rest periods, qualifications). The rising water level naturally enforces hard constraints as forbidden zones.
• Graph partitioning: dividing a chip's circuit graph into balanced parts with few cut edges is a core step in VLSI design, and the Great Deluge has been applied successfully here.
• Vehicle routing: finding good delivery tours under time windows and capacity limits is another domain where the algorithm's deterministic acceptance simplifies parallelization.
• Teaching metaheuristics: because the idea — stay above the flood — is so vivid, the Great Deluge is an excellent first example of how not every good algorithm relies on probability.

Together these uses show that "accept anything above the waterline" is a surprisingly powerful primitive for hard combinatorial problems, complementing approaches like simulated annealing and exact methods.

The Great Deluge algorithm distills a deep idea into a single vivid image: your current solution stands on a landscape, and the water is rising. Every move that keeps you above the flood is allowed; every move that drowns you is forbidden. As the level climbs, bad valleys disappear, and only high-quality ground remains.

The elegance is in what it removes. No temperature. No acceptance probability. No cooling schedule. Just a steadily rising threshold — and the pressure it applies is enough to guide a random walk toward good solutions in a surprisingly wide range of hard problems.

The next time you face a problem too large for exact methods, remember the flood. Sometimes the simplest constraint — stay above the waterline — is all the guidance a search needs.