# Airline scheduling using minimum network flow

Consider the following table for an airline company:

Each flight has an origin-destination airport $i$ and time of departure-arrival airport $i$.

Task: find the minimum number of planes required to perform all flights.

One way of solving this is with minimum network flow:

Nodes $k=1,...5$ represent a flight, $k^\text{'}$ origin node, $k^\text{''}$ destination node, $s$ source node, $t$ sink node. Edges represent all possible valid combinations of flight paths.

Formulating the problem in the LP form:
$$\text{Min} \sum_{j} x_j$$ $$\text{subject to } x_j \in \{0,1\}$$ where $x$ is planes, $j=1,...,5$ is plane number.

Question1: how to complete the LP form?
Question2: what will the coefficients of matrices $A$ and $b$ be for this network?

I do not know of other methods for solving this task, if there is a simpler one, an explanation would be much appreciated.

To complete the LP formulation, add an arc from $t$ to $s$ with a unit cost: a minimum cost flow will minimize the number of units of flow that go from $t$ to $s$, in other words the number of airplanes. Let $x_{ij}\in \mathbb{N}$ be the flow through arc $(i,j)$.
You then want to minimize $x_{ts}$, subject to usual flow conservation constraints.
Note. Another way of doing this is by working with the complement of your graph: add an edge between a destination node and an origin node if and only if the same airplane cannot do both flights. Minimizing the number of airplanes is then equivalent to finding the chromatic number $\chi(G)$ of the graph. By construction, this graph is an interval graph, for which greedy algorithms can optimally color the graph. For example, determine a perfect elimination order of the nodes, and sequentially color them in the reverse order will give you a coloring with exactly $\chi(G)$ colors, in linear time.
• LP for the chromatic number: binary variables $y_i$ if color $i$ is used, $x_{vi}$ if node $v$ takes color $i$. You want to minimize $\sum_i y_i$ subject to $\sum_i x_{vi}=1$ for all $v$, $x_{ui}+x_{vi}\le y_i$ for all edges $(u,v)$. – Kuifje Feb 19 '16 at 19:45