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.
Best Answer
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.