Skip to content

Rounding Heuristic

Definition

A rounding heuristic solves an integer program's LP relaxation and converts fractional variable values to nearby integers. The rounded vector is only a candidate: all original constraints must be checked before accepting it as a feasible solution.

Interpretation

The rounding heuristic is the quickest way from an LP relaxation to an integer candidate: take the relaxed optimum and replace each fractional value by a nearby integer. The result comes with no guarantee: coupled constraints can make the nearest rounded decisions infeasible or substantially worse than an integer optimum.

A feasible polygon with integer points, the LP optimum (3.5, 1.25), and two rounded points: (4, 1), which is infeasible, and (3, 1), which is feasible.

The LP optimum (3.5,1.25)(3.5,1.25) has two natural roundings. Rounding x1x_1 up gives (4,1)(4,1), which violates x1≤3.5x_1\le3.5 and 2x1+2x2≤9.52x_1+2x_2\le9.5; rounding it down gives (3,1)(3,1), which is feasible with z=11z=11. Here (3,1)(3,1) is even the integer optimum, but that is luck rather than a property of rounding.

Rounding fails because the constraints couple the variables, while rounding treats each coordinate on its own. An equality shows this most clearly: if x1+x2=3x_1+x_2=3 and the relaxation gives (1.5,1.5)(1.5,1.5), rounding both values up or both down breaks the equality, and only a mixed choice such as (2,1)(2,1) works. This is why the method is a heuristic and why every candidate must be checked against all original constraints. Rounding is most reasonable for large quantities, where a change of less than one unit is small compared with the values.

A feasible rounded point is still useful. Its value is a bound from the feasible side, so together with the LP value it encloses the optimum, here 11≤z∗≤1311\le z^*\le13 by the optimization bounds, and it can serve as a first incumbent in branch-and-bound.

Key Results

  • Rounding up can violate resource upper bounds.
  • Rounding down can violate minimum requirements or equalities.
  • Even a feasible rounded solution need not be optimal.
  • The video's numerical rounding illustration has inconsistent written constraints and a plotted feasible region; its claimed optimum is not used here.

Examples

  • Rounding (2.6,1.6)(2.6,1.6) upward to (3,2)(3,2) violates 4x1+x2≤124x_1+x_2\le12 because the left-hand side is 14.
  • The nearby vector (2,2)(2,2) satisfies that capacity inequality, but its objective value alone does not prove optimality.

Prerequisites

Sources

Last updated: 20 October 2026 03:02