Consider the problem
min x1 + x2 + x3
6x1 + 7x2 + 8x3 ≥ 51
xi ∈ {0, 1, 2, 3}, all i
Solve the problem by branching. At each node, first propagate the inequality
constraint to reduce domains (if possible). Then solve the LP relaxation, unless the domains are already singletons or empty. Branch on fractional variables. Construct a proof tree analogous to Fig. 4.4. Now derive conditions
under which perturbation of the inequality constraint (coefficients and RHS)
does not reduce the optimal value. Hints: In the analysis of Secction 4.7.3,
there is no propagation, and sensitivity analysis depends only on LP relaxations at the leaf nodes. Here, the situation is reversed. LP relaxations affect
only the branching, and the current optimal value remains optimal as long
as the domain reduction inferences remain valid. Domain reductions at all
nodes (not just leaf nodes) must be considered.