Branch and Bound on Small Mixed-Integer Programs

Extends branch and bound from binary integer programs to mixed-integer programs (MIPs), where integer-required variables may take any nonnegative integer value and other variables may be continuous. Covers branching with floor/ceil constraints, pruning by infeasibility, integrality, and bound, and tracing the full algorithm on small instances.

Step 1 of 157%

Tutorial

Introduction

A mixed-integer program (MIP) is an optimization problem in which some variables must take integer values while others may be continuous. Unlike a binary IP, where integer variables are restricted to $\{0,1\}$ , the integer variables in a general MIP can take any nonnegative integer value: $0, 1, 2, 3, \ldots$

To solve a MIP via branch and bound, we first solve its LP relaxation — the LP obtained by dropping every integrality constraint. If the LP optimum is already integer-feasible in every integer-required variable, we are done. Otherwise, we pick an integer-required variable $x_j$ whose LP value $v$ is fractional and split the problem into two subproblems:

\text{Left child: original LP } + \, (x_j \leq \lfloor v \rfloor)

\text{Right child: original LP } + \, (x_j \geq \lceil v \rceil)

The interval $\lfloor v \rfloor < x_j < \lceil v \rceil$ is forbidden in both children, yet every integer-feasible point of the original MIP still lies in one of them.

For example, if the LP relaxation gives $x_1^* = 2.7$ for an integer-required variable, then $\lfloor 2.7 \rfloor = 2$ and $\lceil 2.7 \rceil = 3$ , so the children add $x_1 \leq 2$ and $x_1 \geq 3$ , respectively.

When several integer-required variables are fractional in the LP, a standard rule is to branch on the most fractional one — the variable whose fractional part is closest to $0.5$ .