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:
                                                        enter image description here
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.

  • $\begingroup$ Would finding the chromatic number help me in formulating a LP? i.e. Could I formulate a different/simpler LP knowing that information? $\endgroup$ – user2974951 Feb 18 '16 at 14:37
  • $\begingroup$ Yes you could, but it would not be a good idea: if you formulate an LP, you will have to solve it with integer programming, which could take a long time. $\endgroup$ – Kuifje Feb 18 '16 at 15:33
  • $\begingroup$ Suppose that is not an issue, I have the information about which node has which color, how would i proceed from here? $\endgroup$ – user2974951 Feb 19 '16 at 18:45
  • $\begingroup$ 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)$. $\endgroup$ – Kuifje Feb 19 '16 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.