Decomposition Methods for Large-Scale Integer Programs

The Bertsimas-Patterson ATFM integer program has binary variables $w_{f,j,t}$ for every flight $f \in F$, sector $j \in J$, and time period $t \in T$. For realistic instances ($|F|\sim 10^4$, $|J|\sim 10^2$, $|T|\sim 10^3$), this yields tens to hundreds of millions of variables — far beyond the reach of off-the-shelf branch-and-bound solvers.

Decomposition methods exploit a key observation: the constraints split into two qualitatively different groups.

Local (per-flight) constraints involve only the variables of a single flight $f$:

• Time monotonicity: $w_{f,j,t} \le w_{f,j,t+1}$
• Sector ordering along the planned route: $w_{f,j',t} \le w_{f,j,t}$ when sector $j$ precedes $j'$
• Completion at the destination: $w_{f,\,\text{dest}(f),\,T} = 1$

Coupling (linking) constraints sum over all flights:

• Sector capacities: $\sum\limits_{f \in F} (w_{f,j,t} - w_{f,j',t}) \le C_{j,t}$
• Airport arrival/departure capacities at each time period

If we removed the coupling constraints, the remaining problem would split into $|F|$ independent per-flight subproblems, each a small shortest-path-style IP on a time–space network. This is block-angular structure, and every decomposition method we will study exploits it: handle the linking constraints carefully so that everything else decomposes.