Minimum covering problem formulation 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 &amp;\sum_{j=1}^{m}c_jx_j\\
&amp;\sum_{v_i \in E_j}x_j&amp;\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 &amp;\bar w.\bar x\\
&amp;A.\bar x &amp;\ge \bar 1\\
&amp;\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.