Master-Subproblem Communication Patterns

Once a large problem has been decomposed into a coordinating master problem and one or more smaller subproblems, the algorithm must specify what information is exchanged between them. This lesson introduces the general master-subproblem loop, the two main communication patterns (price-directive and resource-directive), and the termination conditions used in each.

Step 1 of 157%

Tutorial

The Master-Subproblem Loop

A decomposition algorithm splits a large problem into a coordinating master problem and several smaller subproblems — one per block. The master and the subproblems exchange information through a single structured channel.

The master sends each subproblem $k$ a signal $\sigma_k$ .
Each subproblem $k$ solves its block (parameterized by $\sigma_k$ ) and returns a reply $r_k$ .

The algorithm proceeds in rounds:

\text{Master}\;\xrightarrow{\;\sigma_k\;}\;\text{Subproblem }k\;\xrightarrow{\;r_k\;}\;\text{Master}.

At each round the master inspects the replies, decides whether to terminate, and otherwise updates its signals before the next round.

A key point: subproblems never communicate with each other directly. All coordination flows through the master. This isolation is exactly what allows the subproblems to be solved in parallel.

For instance, a hospital network has three clinics and a central office that allocates the daily nursing budget. The central office (master) sends each clinic $k$ a budget $\sigma_k$ , and each clinic (subproblem) returns the number of patients $r_k$ it can serve under that budget. If $\sigma_1 = 4000,\ \sigma_2 = 3000,\ \sigma_3 = 5000$ and the clinics reply $r_1 = 50,\ r_2 = 35,\ r_3 = 70$ , the central office records that the network served $50 + 35 + 70 = 155$ patients.