Heuristic¶

Definition¶

A heuristic is a solution method designed to obtain a good feasible solution without a general guarantee that it is optimal. In this course, a heuristic solution is required to satisfy the original problem's constraints.

Interpretation¶

A heuristic gives up the guarantee of optimality in exchange for speed or simplicity: a good decision that can actually be carried out is often needed when an exact optimum is too hard or too slow to find.

The figure is drawn for maximization. The heuristic value $z_H$ lies on the left: the heuristic solution is one of the feasible candidates, so the unknown optimum $z^*$ is at least as large. The optimal value $z_R$ of a relaxation lies on the right, and the gap $z_R-z_H$ is the most that accepting the heuristic answer can lose. For minimization the picture is mirrored, and $z_H$ is an upper bound.

Feasibility is required: an answer that breaks a constraint is not acceptable, however good its value. "No general guarantee" does not mean a poor answer: first fit may well find an optimal solution, but cannot prove it by itself; a bound from elsewhere equal to $z_H$ would.

Key Results¶

• For minimization, a feasible heuristic value is an upper bound on the optimum.
• For maximization, a feasible heuristic value is a lower bound.
• A relaxation can supply an opposing bound that measures solution quality.

Examples¶

For maximization, improved incumbents raise the feasible lower bound. Resolving branch-and-bound nodes can reduce the global upper bound formed from the incumbent and the remaining open-node relaxation bounds.

• In the vehicle routing problem, visiting each routing location separately from the depot gives a feasible starting plan.
• First-fit packs items into the first container with enough remaining capacity.

Prerequisites¶

• Feasible Solution
• Optimal Solution

Related Concepts¶

• Relaxation
• Optimization Bounds
• First-Fit Heuristic
• Silver-Meal Heuristic

Sources¶

• OR Modelling · Week 1

Last updated: 20 October 2026 03:02