Branching on a Fractional Variable

How to split a branch-and-bound subproblem into two children by adding floor and ceiling constraints on a fractional LP variable, how to select which fractional variable to branch on, and how the resulting LP bounds drive pruning.

Step 1 of 157%

Tutorial

Introduction to Branching

Branch and bound solves an integer program by relaxing the integrality constraints, solving the resulting linear program (LP), and splitting the problem when the LP solution is not integer-valued.

Branching on a fractional variable. Suppose the LP relaxation at the current node returns a solution x∗\mathbf{x}^* in which some component xj∗=vx_j^* = v is not an integer. We split the current subproblem into two children:

  • Down branch: add the constraint xj≤⌊v⌋.x_j \le \lfloor v \rfloor.
  • Up branch: add the constraint xj≥⌈v⌉.x_j \ge \lceil v \rceil.

This split is valid because every integer value of xjx_j either satisfies xj≤⌊v⌋x_j \le \lfloor v \rfloor or xj≥⌈v⌉x_j \ge \lceil v \rceil — no integer can lie strictly between consecutive integers. The fractional point xj=vx_j = v is excluded from both children, which forces the LP relaxations of the children toward integer feasibility.

For example, if x2∗=3.7,x_2^* = 3.7, we branch into

x2≤3andx2≥4.x_2 \le 3 \quad \text{and} \quad x_2 \ge 4.
↑ ↓ navigate · Enter open · Esc close · ⌘K/Ctrl K toggle