GRASP

When a combinatorial problem is too hard to solve exactly, practitioners reach for metaheuristics — general strategies that trade the guarantee of optimality for the practical ability to find very good solutions quickly. Most metaheuristics come with tuning knobs, populations, or memory structures that require significant engineering. GRASP is the refreshing exception.

Greedy Randomized Adaptive Search Procedures were introduced by Feo and Resende in 1989 and formally published in 1995. The idea is almost embarrassingly simple: build a candidate solution from scratch using a greedy-randomized rule, then improve it with local search, and repeat until a time or iteration budget runs out. Keep the best solution seen across all repetitions.

That two-step loop — construct, then improve — sounds too plain to be competitive. Yet GRASP consistently outperforms pure greedy heuristics, matches or beats many more elaborate metaheuristics on a wide range of scheduling and set-cover problems, and requires almost no problem-specific tuning. Its secret is the construction phase: rather than always making the single best greedy choice, GRASP assembles a restricted candidate list (RCL) of the top-$\alpha$% of available moves and picks one at random. That tiny dose of randomness produces diversity across iterations without the overhead of maintaining a population.

GRASP belongs to the broader family of approximation and heuristic methods that attack NP-hard optimization problems. It has been applied successfully to hundreds of problem classes, from vehicle routing and job scheduling to network design and bioinformatics.

Below is a job-scheduling problem: assign 8 jobs to 3 machines to minimize the makespan (the finish time of the last machine). Greedy always assigns each job to the currently least-loaded machine — it never looks back. GRASP does the same thing, but during construction it randomly picks from the best 40 % of available jobs rather than always the very best one, then applies a local-search swap pass to polish the result.

<p class="hint">{{hint}}</p>
<div class="controls">
  <button id="btn-greedy" type="button">{{btn_greedy}}</button>
  <button id="btn-grasp" type="button">{{btn_grasp}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="results" class="results hidden">
  <div class="result-row">
    <span class="label greedy-label">{{label_greedy_makespan}}</span>
    <span id="greedy-span" class="val">—</span>
  </div>
  <div class="result-row">
    <span class="label grasp-label">{{label_grasp_makespan}}</span>
    <span id="grasp-span" class="val">—</span>
  </div>
  <div class="result-row gap-row">
    <span class="label">{{label_improvement}}</span>
    <span id="gap-span" class="val gap">—</span>
  </div>
</div>
<div id="chart" class="chart"></div>
<p id="log" class="log"></p>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .9rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.results { margin-bottom: .8rem; }
.results.hidden { display: none; }
.result-row { display: flex; align-items: center; gap: .6rem; margin: .25rem 0; font-size: .9rem; }
.label { min-width: 160px; color: #555; }
.val { font-weight: 700; font-size: 1rem; }
.gap { color: #0a7d33; }
.gap-row { margin-top: .3rem; }
.greedy-label::before { content: ""; display: inline-block; width: 10px; height: 10px; background: #adb1b8; border-radius: 2px; margin-right: 5px; }
.grasp-label::before { content: ""; display: inline-block; width: 10px; height: 10px; background: #1d3557; border-radius: 2px; margin-right: 5px; }
.chart { display: flex; flex-direction: column; gap: 6px; }
.machine-row { display: flex; align-items: center; gap: 6px; }
.machine-label { min-width: 24px; font-size: .78rem; color: #555; font-weight: 600; }
.bar-track { flex: 1; background: #eee; border-radius: 4px; height: 28px; position: relative; overflow: hidden; }
.bar-seg { position: absolute; top: 0; height: 100%; border-right: 2px solid #fff; display: flex; align-items: center; justify-content: center; font-size: .7rem; font-weight: 700; color: #fff; overflow: hidden; transition: all .35s; }
.bar-seg.greedy { background: #adb1b8; }
.bar-seg.grasp { background: #1d3557; }
.makespan-line { position: absolute; top: 0; height: 100%; border-right: 2.5px dashed #e63946; }
.log { font-size: .82rem; color: #555; margin-top: .6rem; min-height: 1.2em; }

// Code not found

Click Run Greedy to see the deterministic result. Click Run GRASP (×20) to run 20 independent GRASP iterations and keep the best. Notice how GRASP consistently finds a shorter or equal makespan — and that the best-of-20 gap over pure greedy grows the more you click.

GRASP is a heuristic, not an exact algorithm, so it carries no approximation ratio guarantee in general. What makes it interesting is the interaction between its two phases:

Construction phase. At each step, the algorithm evaluates all remaining elements by a greedy criterion (e.g., the job whose addition increases makespan the least). It places the top-$\alpha$% in the Restricted Candidate List (RCL) and picks one uniformly at random. Setting $\alpha = 0$ gives pure greedy; $\alpha = 1$ gives a purely random construction. The key insight is that moderate $\alpha$ values (often 0.2–0.4 in practice) inject enough diversity to escape greedy's local traps without sacrificing too much construction quality.

Local search phase. After construction, GRASP runs a local improvement procedure — typically swapping two elements or moving one element to a different position — until no single move reduces cost. This is equivalent to finding a local optimum in the neighborhood structure. Because construction already produces a reasonable starting point, local search converges quickly.

Why it works. Each GRASP iteration produces an independent local optimum from a different starting point. The probability that the global optimum lies in the basin of attraction of at least one starting point grows with the number of iterations. Probabilistic analysis by Feo, Resende, and others shows that under mild conditions, the expected solution quality converges to the optimum as iterations $\to \infty$.

No tuning, no memory. Unlike simulated annealing (which has a cooling schedule) or tabu search (which maintains a forbidden-moves list), GRASP has essentially one parameter: $\alpha$. There is no population to manage, no pheromone matrix to update, no crossover operator to design. This simplicity makes GRASP an ideal baseline before investing in more complex methods.

The underlying scheduling and routing problems GRASP is applied to are typically NP-hard, so no polynomial-time exact algorithm is known unless P = NP.

GRASP's generality has led to successful applications across an unusually wide range of domains:

• Job and machine scheduling: minimizing makespan or total weighted completion time on parallel machines — problems where greedy alone misses interactions between jobs.
• Vehicle routing: assigning delivery routes to vehicles to minimize total distance, a classic NP-hard problem with huge economic impact.
• Network design: selecting edges to connect nodes under cost or reliability constraints, crucial for telecommunications and supply chains.
• Set cover and facility location: choosing the smallest subset of facilities that covers all demand points.
• Bioinformatics: sequence alignment, phylogenetic tree construction, and protein structure prediction all benefit from GRASP's ability to explore diverse local optima.
• VLSI placement and routing: arranging transistors on a chip so that wire lengths are minimized.

Because GRASP is so easy to implement, it is often the first metaheuristic tried on a new problem. If it performs well, the search stops. If not, the GRASP solution serves as a benchmark for evaluating more complex methods. In competitive operations-research contexts, GRASP solutions seeded into hybrid algorithms — combining GRASP construction with exact branch-and-bound or genetic crossover — routinely reach state-of-the-art results.

GRASP is a masterclass in the power of simplicity. Its two-step loop — build greedily with a random twist, then improve locally — needs almost no tuning, applies to virtually any combinatorial problem, and consistently outperforms the deterministic greedy heuristics that practitioners reach for first.

The key insight is that diversity during construction is cheap and effective. A small random element in an otherwise greedy procedure is enough to explore a wide region of the solution space across iterations, while local search guarantees that each iteration ends at a high-quality local optimum rather than wherever the random walk happened to stop.

If you ever need to attack a scheduling, routing, or assignment problem and lack the time to engineer a specialized solver, GRASP is where to start. It will almost certainly beat pure greedy, and it might save you from needing anything more elaborate at all. The underlying problems remain NP-hard — GRASP does not change that — but it narrows the practical gap between what we can compute and what we wish we could.