Restricted Master Problem and Pricing Subproblem

In a column generation scheme, the master problem is a linear program of the form

$$\min \; c^T x \quad \text{subject to} \quad Ax \geq b, \; x \geq 0,$$

in which the coefficient matrix $A$ has so many columns that we cannot enumerate them all. We don't attempt to solve it directly. Instead, we maintain a restricted master problem (RMP) — the same LP using only a subset $S$ of the columns:

$$\min \; \sum_{j \in S} c_j x_j \quad \text{s.t.} \quad \sum_{j \in S} a_j x_j \geq b, \; x_j \geq 0.$$

Because $|S|$ is small, the RMP is an ordinary LP we can solve directly. Solving it produces two outputs:

• a primal solution $x^*$, using only columns in $S$ (columns outside $S$ are implicitly fixed at $0$);
• a vector of dual variables $\pi = (\pi_1, \ldots, \pi_m)$, one for each of the $m$ master constraints.

For example, consider the master problem

$$\min 3x_1 + 5x_2 + 4x_3 + 7x_4 \quad \text{s.t.} \quad \begin{cases} x_1 + 2x_2 + x_3 + 3x_4 \geq 6 \\ 2x_1 + x_2 + 4x_3 + x_4 \geq 5 \end{cases},\; x_j \geq 0.$$

Restricting to $S = \{2, 3\}$ produces the RMP

$$\min 5x_2 + 4x_3 \quad \text{s.t.} \quad 2x_2 + x_3 \geq 6, \; x_2 + 4x_3 \geq 5, \; x_2, x_3 \geq 0.$$

The dual $\pi$ is the critical output: it is what the next stage — the pricing subproblem — uses to decide which column outside of $S$ should enter.