Can it accept a worse solution?

Yes, if the candidate still satisfies the current acceptance boundary under the chosen rule.

Does the water level always increase?

It increases in a maximization convention; a minimization formulation commonly tightens an upper bound downward.

Does it guarantee the optimum?

No. An ordinary heuristic run returns the best solution it found, without a general global-optimality certificate.

AI Glossary / Mathematics and optimization / Intermediate

Great deluge algorithm

Definition

The Great deluge algorithm is a local-search optimization heuristic that accepts candidate solutions according to a changing quality threshold. It can permit a move that worsens the current solution while still meeting the threshold, helping the search move beyond a local optimum. The threshold gradually becomes more demanding. The method was introduced by Gunter Dueck and does not guarantee finding a global optimum in an ordinary finite run.

What it means

An optimization search needs both a way to propose nearby solutions and a rule for accepting them. Always accepting only immediate improvements can trap a search where every available move looks worse, even when better solutions exist beyond that neighborhood.
Great deluge allows controlled deterioration relative to the current solution. Its threshold is an absolute score boundary, not simply a permitted change from the current score. The current solution, the best solution found, and the current threshold are three different quantities and should be tracked separately.

How it works

For a maximization convention, begin with a solution and a lower acceptance boundary called the water level. Propose a neighboring solution, accept it if its score meets the current boundary, and raise the boundary according to the chosen schedule. Retain the best solution encountered.
For minimization, the corresponding acceptable upper bound generally decreases. Implementations differ in strict versus inclusive comparisons, threshold updates, and stopping rules. The worked example uses an explicit iteration-based schedule so every decision is reproducible. The acceptance test can be deterministic even when candidate generation uses randomness.

Three practical examples

A scheduling experiment can explore feasible timetables while allowing temporary increases in soft-constraint penalties under a minimization version.
A routing prototype can compare threshold-based acceptance with improvement-only local search on a fixed evaluation budget.
A search-method study can examine how a faster or slower threshold schedule changes exploration and final solution quality.

Think of it this way

Imagine walking among hills while floodwater rises. You may move downhill temporarily if the new location remains above water, but the growing water level steadily removes low routes. The analogy is limited: an optimization landscape is a set of encoded solutions, and the schedule is designed by the algorithm rather than governed by a real flood. Surviving above the threshold does not prove that the highest hill was found.

Worked example

Consider an original maximization exercise with feasible solutions and a stipulated sequence of proposed neighbors. Start at score 10, with best-so-far score 10 and water level 8. Accept a proposal when its score is at least the current water level. After every proposal, including a rejected one, increase the water level by one. Stop after five proposals.
At iteration one, the proposed score is 9. It is worse than the current score 10 but meets the boundary 8, so accept it. The current score becomes 9, the best remains 10, and the next water level becomes 9.
At iteration two, the proposal scores 8. It fails the boundary 9, so reject it. Current and best remain 9 and 10 respectively, while the boundary advances to 10. At iteration three, a proposed neighbor scores 12 and passes the boundary 10. Accept it, update the best to 12, and raise the boundary to 11.
At iteration four, the proposed score is 11. Inclusive comparison accepts it at boundary 11, even though it worsens the current score 12. The current score becomes 11, best stays 12, and the boundary becomes 12. At iteration five, a proposal scores 10 and is rejected. The current solution still scores 11, but the best recorded solution scores 12 and is the appropriate returned incumbent under this example's rule.
The trace shows two important distinctions. Accepted moves need not improve the incumbent, and the final current solution need not be the best encountered. The neighbor sequence is illustrative.
Changing the update rule to advance only after accepted moves would change later boundaries. Changing at least to strictly greater would reject iteration four.

Illustrative case study

Fictional case: a training provider experiments with room-allocation schedules. It uses a cost for inconvenient room changes while enforcing mandatory capacity constraints separately. A Great deluge search sometimes ends at a schedule worse than one visited earlier.
The team fixes its reporting to return the best feasible schedule recorded, documents the threshold schedule, and compares several runs with an improvement-only baseline. It reviews feasibility independently of the heuristic's soft score and avoids describing the result as globally optimal without a separate proof.

Common misconceptions and mistakes

Do not confuse the threshold with a probability of accepting a worse move. The stated comparison is a score test. Do not conclude that the entire search is deterministic merely because the acceptance rule is deterministic; random move generation can still vary the trajectory.
Also distinguish an absolute boundary from threshold accepting based on score differences. A very demanding schedule can close escape routes too early, while a permissive schedule can spend much of the budget wandering. Neither slow tightening nor long runtime by itself certifies optimality.

Business use

Great deluge can be a relatively simple candidate for optimization tasks where a useful solution is needed within a limited budget. Its practical value depends on the neighborhood, scoring function, feasibility handling, and threshold schedule.
Keep a strong baseline and compare quality at equal computational effort. Record starting solutions, random seeds where applicable, and all acceptance conventions. Use multiple representative instances and report variability. Separate the objective value from business measures such as disruption or operating effort, ensuring that the score actually represents the decision the organization wants to improve.

Check your understanding

Why should the worked example return score 12 rather than the final current score 11?

Answer: Score 12 is the best solution encountered. A later accepted deterioration changed the current solution but should not erase the saved best incumbent.

Related terms

Local search
Hill climbing
Simulated annealing
Neighborhood
Metaheuristic
Threshold accepting
Record-to-record travel
Incumbent
Acceptance criterion

Learn next

Repeat the five-proposal trace using strict greater-than acceptance instead of an inclusive comparison. Then repeat it with threshold updates only after acceptance. Identify which decisions change and explain why a published result needs these conventions to be reproducible.

Sources

Original research attribution: Dueck, New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-Record Travel: https://www.sciencedirect.com/science/article/pii/S0021999183710107 . Primary implementation explanation: OptaPlanner Great Deluge documentation: https://www.optaplanner.io/docs/optaplanner/latest/local-search/local-search . Original paper abstract and implementation description consulted; the iteration trace is original and explicitly specifies its variant.

Previous: Gray-world assumption Next: Greedy agent