Shouldn't I post this question on mathematics.stackexchange.com?

Let be an airlaine company which has to affect its aircrew to several flights. We group som flights in subset, every flights of a subset have to be realised by the same aircrew according to the actual possibilites and labour regulations. We provide a list, as rich a way as possible, of those combinations. Let be $E_j$ the $j^{th}$ combination. We associate to $E_j$ a cost $c_j$ that take into account, for instance, the bonuses to aircrew for a time worked that would outreach th norms, etc...

The problem is to determine the combinations such that all flights are covered and that the cost is the minimal one.

I have to give a formulation of this problem as a linear programing problem.

The set of flights $V=\{v_1;...;v_m\}$

Let be $x_j= \begin{cases} 1 \mbox{ if the combination $E_j$ is taken}\\ 0 \mbox{ else} \end{cases}$

I don't understand the following formulation by my teacher. \begin{cases} \min &\sum_{j=1}^{m}c_jx_j\\ &\sum_{v_i \in E_j}x_j&\ge 1\\ \end{cases}

But I quite understand the one given by Vangelis Paschos in Combinatorial Optimization:

An instance of the MIN WEIGHTED VERTEX COVER. An instance of this problem (given the incident matrix $A$, of dimension $m\times n$, of a gaph $G(V,E)$ of order $n$ with $|E|=m$ and a vector $\bar w$, of dimension $n$ of the costs of the edges $V$), can be expressed in terms of linear program in integers as

$$\begin{cases} \min &\bar w.\bar x\\ &A.\bar x &\ge \bar 1\\ &\bar x \in \{0;1\}^n \end{cases}$$

such that $x_i=1$ if the vertex $v_i\in V$ is included in the solution $x_i = 0$ if it is not included. The block of $m$ constraints $A.\bar x \ge \bar 1$ expresses the fact that for each edge at least one of these extremes must be included in the solution.

But I don't quite understand this notation $\bar 1$

The feasible solutions are all the transversals of $G$ and the optimum solution is a transversal of $G$ of minimum total weight, that is a transversal corresponding to a feasible vector consisting of a maximum number of 1.


Typically $\bar{1}$ represents the vector of 1s. In this case, $A\bar{x} \ge \bar{1}$ enforces the vertex cover constraint. The two formulations are the same, except the latter uses a more compact matrix notation to represent the inequality for each of the $j$ variables.


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.