Algorithm¶

Definition¶

An algorithm is a prescribed sequence of computational rules for solving a problem. In the iterative methods considered in the course, these rules are applied repeatedly; each repetition is an iteration.

Interpretation¶

An algorithm turns a problem into a list of steps that can be carried out mechanically. In an iterative method the same rule is applied again and again, and a stopping condition says when the work is finished.

A flowchart: start from an initial solution, apply the rule once, check the stopping condition, and either loop back for another iteration or output the answer.

The flowchart shows the three parts of an iterative method: a starting point, a rule for one iteration, and a stopping test that ends the method or sends it back for another round. The output box also names what is known about the answer when the method stops.

That guarantee separates an exact method, whose answer is known to be optimal, from a heuristic such as first fit, which guarantees only a feasible answer. "Algorithm" says that the procedure is fully specified, not how good its answer is.

Key Results¶

The simplex method, network algorithms, and dynamic programming use different problem structures.
An iteration need not strictly improve the objective: a degenerate simplex pivot can leave its value unchanged.
A heuristic is a solution procedure without a general guarantee of optimality.

Examples¶

Simplex checks its objective-row sign condition; the shortest-path method settles vertices until the destination is reached; flow augmentation stops when no augmenting path remains; dynamic programming advances through stages.

A simplex iteration exchanges a basic and a nonbasic variable.
A spanning-tree algorithm repeatedly adds an eligible edge.

Prerequisites¶

Optimization Model

Sources¶

OR Modelling · Week 1

Last updated: 20 October 2026 03:02