Heuristic

A heuristic is a class of algorithms that delivers reasonable-quality solutions in polynomial time without guaranteeing optimality. Systematic use of the term in OR spread in the 1960s-1970s following Polya's *How to Solve It* (1945) and the rise of NP-Hard problems. Heuristics fall into two broad families: (1) constructive heuristics build a solution step by step from an empty start — examples include Christofides (1976) for TSP, nearest neighbor, the Clarke-Wright savings method, greedy edge insertion in the travelling salesman, and LPT/SPT priority rules in scheduling; (2) improvement heuristics refine an existing solution via small neighborhood moves — 2-opt, k-opt, and Lin-Kernighan (1973) are canonical examples. Heuristics are evaluated on three axes: solution quality (gap to a lower bound), runtime, and implementation complexity. Some heuristics belong to the approximation algorithm class with proven constant performance guarantees (e.g. Christofides' 1.5-approximation for metric TSP); others are only empirically strong. In practice heuristics serve as warm-start input to MIP solvers, primal bound generators, or direct production solutions. Silver, Vidal, and de Werra (1980) and Reeves (1993) are classical references. Metaheuristics (#053) form the umbrella framework on top of heuristics.