The Bertsimas-Patterson ATFM Integer Program

The Bertsimas–Patterson model is the standard integer program for air traffic flow management (ATFM). We are given a set of flights $F$, a set of sectors $J$ (which includes departure and arrival airports), each flight's route $P_f \subseteq J$, and a discretized horizon of time periods $t = 1, 2, \ldots, T$. The model decides when each flight enters each sector along its route.

The key modeling trick is the binary 'by-time-$t$' indicator. For each flight $f$, each sector $j \in P_f$, and each time $t$, define

$$w^f_{j,t} = \begin{cases} 1 & \text{if flight } f \text{ has arrived at sector } j \text{ by time } t, \\ 0 & \text{otherwise.}\end{cases}$$

This encoding has two clean consequences.

Monotonicity in time. Once a flight has arrived, it stays arrived:

$$w^f_{j,t} \geq w^f_{j,t-1}.$$

Arrival at exactly time $t$. The forward difference $w^f_{j,t} - w^f_{j,t-1}$ equals $1$ at the single time step when the flight first reaches sector $j$, and is $0$ everywhere else.

If $j'$ is the sector immediately following $j$ on the route $P_f$, then flight $f$ is physically inside sector $j$ at time $t$ exactly when it has reached $j$ but not yet reached $j'$. Therefore

$$\mathbf{1}[f \text{ in sector } j \text{ at time } t] \;=\; w^f_{j,t} - w^f_{j',t}.$$

This is the formula used throughout the model to count traffic.