Integer Programming and Branch-and-Bound

In many critical decision-making scenarios—from scheduling airline crews to designing communication networks—the best solutions involve discrete, whole-number choices. You cannot build half a factory or launch a third of a satellite. Integer Programming (IP) is the mathematical framework for modeling and solving these combinatorial optimization problems where some or all variables must take integer values. This article guides you through formulating these models and mastering the branch-and-bound algorithm, the cornerstone technique for finding optimal solutions, even when exploring every possible combination is computationally impossible.

1. Formulating Integer and Mixed-Integer Linear Programs

At its core, an Integer Programming problem is a Linear Programming (LP) problem with an added integrality constraint. The general form of a Mixed-Integer Linear Program (MILP) is: $$\begin{array}{rl}\text{Maximize }& {\mathbf{c}}^T\mathbf{x}\\ \text{subject to }& A\mathbf{x}\le \mathbf{b}\\ & \mathbf{x}\ge 0\\ & x_j\in \mathbb{Z}\text{ for }j\in I\end{array}$$ Here, $I$ is a subset of the variable indices. If all variables must be integers, it is a pure Integer Program (IP). A special and extremely useful case is binary variables, where $x_j\in \{0,1\}$, often representing yes/no decisions like whether to open a facility.

Formulation is an art that translates a word problem into precise mathematics. Consider a simple Capital Budgeting problem: you have a list of potential projects, each with an expected profit $p_j$ and capital requirement $c_j$, and a total budget $B$. The goal is to maximize total profit without exceeding the budget. You can model this with binary variables $x_j$, where $x_j=1$ if project $j$ is selected, and $0$ otherwise. The model is: $$\begin{array}{rl}\text{Maximize }& \sum _j{p}_j{x}_j\\ \text{subject to }& \sum _j{c}_j{x}_j\le B\\ & x_j\in \{0,1\}\forall j\end{array}$$ Effective formulation requires identifying the decision variables, objective function, and constraints that accurately capture the problem's logic, especially the discrete nature of choices.

2. The Power and Limits of LP Relaxation

A fundamental concept in solving IPs is the LP Relaxation. This is the problem obtained by removing all integrality constraints, allowing the variables to take any continuous value within their bounds. For a maximization problem, the optimal value of the LP relaxation provides an upper bound on the optimal value of the original IP (for minimization, it provides a lower bound).

Why is this useful? First, solving the LP relaxation is fast using the Simplex or Interior Point methods. Second, if the optimal solution to the LP relaxation happens to satisfy all integrality constraints, then you have fortuitously solved the original IP. Unfortunately, this is often not the case. The solution will typically have fractional values, like choosing 0.7 of a project. The gap between the LP relaxation's solution and the true IP solution defines the challenge. This is where systematic algorithms like branch-and-bound come into play, using the LP relaxation's bound to guide an intelligent search.

3. The Branch-and-Bound Algorithm Explained

Branch-and-bound (B&B) is a clever "divide and conquer" strategy that avoids examining every possible integer solution by pruning large parts of the search tree. It systematically partitions the feasible region and uses bounds from the LP relaxation to decide which parts can be safely ignored.

The algorithm maintains a search tree and a list of active subproblems (nodes). It proceeds as follows:

1. Initialization: Solve the LP Relaxation of the original problem. If the solution is integer, you are done. Otherwise, this node becomes the first active subproblem. Set the best known integer solution (the incumbent) to null.
2. Node Selection: Choose an active subproblem (node) to process. Common strategies are best-bound first (choose node with the best LP objective) or depth-first.
3. Relaxation & Bounding: Solve the LP relaxation for the selected node.

• If it is infeasible, prune the node.
• If its optimal value is worse than the incumbent's value (for maximization), prune by bound.
• If the solution is integer and better than the incumbent, update the incumbent and prune the node.

1. Branching: If none of the above occur, the solution is fractional. Choose a fractional variable, say $x_j=3.4$. Create two new child subproblems by adding new constraints:

• Left Child: $x_j\le 3$
• Right Child: $x_j\ge 4$

This splits the feasible region, eliminating the current fractional solution.

1. Termination: The algorithm terminates when no active subproblems remain. The incumbent is the optimal solution.

The efficiency of B&B hinges on finding good incumbents early (through good heuristics) and generating tight LP relaxations that provide strong bounds, enabling aggressive pruning.

4. Cutting Plane Methods for Stronger Bounds

Cutting plane methods, often used in tandem with branch-and-bound (in a method called branch-and-cut), aim to improve the LP relaxation bound by adding valid inequalities, or "cuts." A cut is a linear constraint that is satisfied by all integer feasible solutions but violated by the current fractional LP solution. By adding this constraint, you "cut off" the fractional solution, forcing the next LP solution to be closer to an integer point.

Consider a simple constraint with binary variables: $x_1+x_2\le 1$. The LP relaxation allows the fractional solution $(0.8,0.8)$. A valid cut like $x_1+x_2\le 1$ is already there, but it's not cutting off the fractional point because it's satisfied ($0.8+0.8=1.6>1$). Wait, that's violated. Let's use a better example. For a knapsack constraint $5x_1+8x_2\le 10$ with binary variables, the fractional solution $(1,0.625)$ is feasible for the LP. A cover inequality can be derived: since the items with coefficients 5 and 8 cannot both be chosen (5+8=13>10), the inequality $x_1+x_2\le 1$ is valid for all integer solutions but cuts off the fractional point $(1,0.625)$. Adding such cuts tightens the formulation, leading to a smaller B&B tree.

5. Application to Classic Combinatorial Problems

The true test of these techniques is their application to complex, real-world problems.

• Scheduling: Assigning jobs to machines with sequence-dependent setup times can be modeled with binary variables $x_{ijt}$ (whether job $j$ follows job $i$ on machine $t$) and continuous time variables. The integrality constraints ensure each job has exactly one predecessor and successor. B&B can be used to find schedules that minimize total makespan or tardiness.
• Facility Location: Deciding where to open warehouses from a set of potential sites to serve customers at minimum cost is a classic MILP. Binary variables $y_i$ indicate if facility $i$ is opened, and continuous variables $x_{ij}$ represent the flow from facility $i$ to customer $j$. The fixed cost of opening facilities makes the problem combinatorial.
• Network Design: Designing a cost-effective telecommunications network involves choosing which links to install (binary decisions) and how to route flow (continuous decisions). Constraints ensure connectivity and capacity. The LP relaxation often gives fractional solutions where links are used at a fraction of capacity; B&B forces the yes/no decisions on which links to build.

Common Pitfalls

1. Poor Formulation Leading to Weak Bounds: A common mistake is creating a mathematically correct but "loose" formulation. The LP relaxation of a weak formulation gives a bound that is far from the true IP optimum, resulting in a massive, inefficient B&B tree. Correction: Always seek the strongest or tightest formulation. Use techniques like introducing additional valid inequalities (even simple ones like $x_i\le 1$ for binaries) or reformulating constraints (e.g., using the "convex hull" representation where possible).
2. Branching on the Wrong Variable: In the branching step, arbitrarily choosing a fractional variable can slow progress. Correction: Use branching rules like most fractional (choose variable whose fractional part is closest to 0.5) or pseudocost branching, which uses historical data on how much branching on a variable has improved the bound in the past.
3. Ignecting the Incumbent (Heuristics): Relying solely on B&B to stumble upon integer solutions can be slow. Correction: Implement simple heuristics at the root node (or throughout the tree) to find a good-quality integer solution early. This provides a strong incumbent, allowing for more pruning by bound from the very beginning.
4. Misinterpreting the LP Relaxation Solution: Viewing the fractional LP solution as an approximate answer is incorrect. A solution suggesting "build 0.7 of a factory" is not practically meaningful. Correction: Understand that the LP solution's primary role is to provide a bound. The integer solution found by B&B is the only operationally valid answer.

Summary

• Integer Programming extends linear programming to model discrete, logical decisions using integer or binary variables, forming the basis for combinatorial optimization.
• The LP Relaxation, by dropping integrality, provides a solvable problem whose optimal value gives a crucial bound on the true IP solution's value.
• The Branch-and-Bound algorithm solves IPs by recursively partitioning the solution space and using LP relaxation bounds to prune suboptimal branches, making exhaustive search unnecessary.
• Cutting Plane Methods improve the LP relaxation by adding valid inequalities that cut off fractional solutions, tightening the bound and accelerating branch-and-bound.
• These techniques are powerfully applied to scheduling, facility location, and network design problems, where discrete choices are fundamental to the optimal solution.