Branch and Bound on Small Binary IPs

A binary integer program (binary IP) is a linear optimization problem of the form

$$\max\; c_1 x_1 + c_2 x_2 + \cdots + c_n x_n$$

subject to linear inequality constraints, where each decision variable satisfies $x_i \in \{0,1\}$.

The LP relaxation drops the integrality requirement and instead allows $0 \le x_i \le 1$. Because every binary-feasible point is also LP-feasible, the LP feasible region contains the binary feasible region. Therefore the LP optimum is an upper bound on the binary IP optimum:

$$z^*_{\text{IP}} \;\le\; z^*_{\text{LP}}.$$

This bound is the engine of branch-and-bound. If the LP relaxation at a subtree returns a value no better than an integer solution already in hand, the entire subtree can be discarded.

For example, consider

$$\max\; 7x_1 + 4x_2 + 5x_3 \quad\text{s.t.}\quad 3x_1 + 2x_2 + 4x_3 \le 6,\;\; x_i \in \{0,1\}.$$

The LP relaxation has optimum $x^* = (1,\,1,\,1/4)$ with value $7 + 4 + 5/4 = 12.25$. Therefore the binary IP optimum is at most $12.25$. The component $x_3 = 1/4$ is fractional, so a branching step will split on $x_3$ next.