
444 Introduction to Computational Models with Python
setting the variable to 0, or setting the variable to 1. More generally, a variable
with lower bound l and upper bound u will be divided into two problems with
ranges l to q and q + 1 to u, respectively. Lower bounds are provided by the
linear optimization relaxation of the problem. If the optimal solution to a
relaxed problem is (coincidentally) integral, it is an optimal solution to the
subproblem, and the value can be used to terminate searches of subproblems
whose lower bound is higher.
25.3.2 Branch and Cut
For branch and cut, the lower bound is again provided by the linear optimiza-
tion relaxa ...