Linear Programming vs Integer Programming

In air routing, optimization models come in two flavors that look almost identical -- but the difference profoundly changes both what they can express and how hard they are to solve.

A linear program (LP) optimizes a linear objective over a feasible region defined by linear inequalities. Its decision variables are continuous:

$$\begin{array}{rl}\text{maximize} & \mathbf{c}^\top \mathbf{x} \\ \text{subject to} & A\mathbf{x} \leq \mathbf{b} \\ & \mathbf{x} \geq \mathbf{0}.\end{array}$$

An integer program (IP) has the same form but with an extra integrality requirement:

$$\begin{array}{rl}\text{maximize} & \mathbf{c}^\top \mathbf{x} \\ \text{subject to} & A\mathbf{x} \leq \mathbf{b} \\ & \mathbf{x} \geq \mathbf{0},\ \mathbf{x} \in \mathbb{Z}^n.\end{array}$$

A binary integer program (BIP) restricts variables to $\{0,1\}$, modeling yes/no decisions.

The choice between LP and IP comes from the nature of each decision variable in the routing problem:

• Liters of fuel, traffic densities, fractions of capacity used $\Rightarrow$ LP.
• Number of flights scheduled, aircraft assigned, crews dispatched $\Rightarrow$ IP.
• Whether a route is opened, a slot allocated, an aircraft used $\Rightarrow$ BIP.

The integrality requirement looks small but has huge computational consequences: LPs are solvable in polynomial time, while general IPs are NP-hard.