Branch and bound and valid bounds

For integer maximization, any feasible integer solution gives a lower bound on the unknown optimal value. The best one found so far is the incumbent. A maximized LP relaxation gives an upper bound because its feasible set contains all integer-feasible points of that node. Reversing either direction can wrongly discard the optimum. The relaxed optimum is not itself an incumbent unless its integer-restricted coordinates satisfy the required integrality and all original constraints. Rounding a fractional vector is merely a candidate-generation heuristic until feasibility is checked again.

An exact optimal LP value is one source of a node upper bound, but a feasible LP dual vector also provides a valid bound without requiring primal optimality. For a maximization LP, a partially optimized primal point alone does not supply such an upper bound. This matters when numerical LP solves terminate early. If the integer objective is known to be integer-valued, a valid real upper bound can be rounded downward; otherwise that strengthening is unjustified. Bounds must include all constant terms and scaling used when translating the objective.

If a node relaxation has a fractional integer-restricted coordinate $x_j=\alpha$, create children with $x_j\le\lfloor\alpha\rfloor$ and $x_j\ge\lceil\alpha\rceil$. Every integer value satisfies exactly one side, so no integer-feasible point is lost. The branch is not a claim that the parent optimizer survives in either child; removing that fractional point is intentional. A child can be pruned when it is infeasible, when its valid upper bound is no greater than the incumbent, or when its relaxation has an integer-feasible optimizer attaining that bound.

The search ends with a global certificate when every node has been pruned or solved. With live nodes, the largest valid upper bound among them, combined with the incumbent, bounds the global optimum. If no incumbent exists, there is no achieved lower bound to report as a feasible answer. If no live nodes remain and no incumbent was ever found, the original integer model is infeasible. Node-selection strategies and branching heuristics can greatly alter runtime, but they must preserve coverage of all unresolved integer possibilities and the validity of every bound used for deletion.

For a pure integer problem with finite bounds on every variable, exhaustive branching can eventually isolate all integer assignments, giving a finite exact search. This does not provide a polynomial worst-case guarantee: the number of assignments and the branch tree can grow exponentially. Unbounded integer domains need additional assumptions and algorithmic treatment before a termination claim is justified. General mixed-integer linear programming retains hard discrete structure even though each node relaxation is a polynomially solvable continuous LP. Small integrality gaps and strong bounds often help, but they do not alone guarantee a small tree.

In floating-point implementations, integrality tolerances, feasibility tolerances, and bound tolerances serve different purposes. A coordinate near an integer does not make a resource violation acceptable, and an optimistic rounded upper bound can invalidate pruning. Certified workflows use validated dual bounds, directed rounding, or exact arithmetic where necessary. Report an absolute gap $U-L$ along with feasible incumbent data and a clear relative-gap convention; relative gaps become delicate near zero or when objectives have opposite signs. A time-limited run with a nonzero certified gap is an honest partial result, not a proof of optimality.