Minimum covering problem formulation

Question

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.

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