Skip to content

Optimization Bounds

Proposition

Suppose an optimization problem has a finite optimal value z∗z^*. Let zHz_H be the value of a feasible solution and zRz_R the finite optimal value of a relaxation with the same objective. Then

zR≤z∗≤zHfor minimization,z_R\le z^*\le z_H\quad\text{for minimization},
zH≤z∗≤zRfor maximization.z_H\le z^*\le z_R\quad\text{for maximization}.

Interpretation

The two bounds trap the unknown optimum between a value that is known to be achievable and a value that cannot be beaten. Their difference measures how much the current feasible solution could still be improved, without knowing the optimum itself.

A horizontal line of objective values with the value of a feasible solution on the left, the value of a relaxation on the right, the unknown optimum between them, and the gap marked.

The figure is drawn for maximization. The value zHz_H of a feasible solution lies on the left and the optimal value zRz_R of a relaxation on the right; the unknown z∗z^* lies somewhere between them. The gap zR−zHz_R-z_H is the largest possible loss from accepting the feasible solution.

Each inequality has a short reason. The feasible solution is one of the points over which the optimum is taken, so the optimum is at least as good as zHz_H. The relaxation optimizes the same objective over a larger set FR⊇FF_R\supseteq F, so its optimum is at least as good as z∗z^*. This is why the relaxed value must be an optimal value and the other must come from a feasible point: an infeasible point says nothing about z∗z^*.

The direction words switch with the problem type, but the order does not: the feasible value is always on the worse side and the relaxed value on the better side. For minimization a heuristic gives an upper bound and a relaxation a lower bound; in the vehicle routing problem this gives 202≤z∗≤214202\le z^*\le214 miles.

Key Results

  • For a minimization problem, zH−z∗≤zH−zRz_H-z^*\le z_H-z_R.
  • If the feasible and relaxed values coincide, the feasible solution is proven optimal.
  • A feasible solution of a relaxation alone is not generally an opposing bound; its optimal value is needed.

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.

  • The routing example gives 202≤z∗≤214202\le z^*\le214, so the remaining improvement is at most 12 miles.
  • A 232-mile route is also an upper bound, but 214 is tighter.

Prerequisites

Sources

Last updated: 20 October 2026 03:02