MILP formulation for minimum set Vertex cover problem

Question

I’m sorry to bother you with this simple question. I would like to model a simple model of the minimum cover vertex set problem. I believe that the original problem is such as

$$ \min \quad \sum_{v\in V} x_v $$ subject to $$ x_u + x_v \ge 1 \quad \forall (u,v) \in E $$ $x_v$ is a binary variable, which takes value $1$ if vertex $v$ is included in the minimum set and $0$ otherwise. I have added another binary variable $z_{uv}$ with the following constraint $$ \sum_{(u,v)\in E} z_{uv} \ge k $$ where $k$ is a parameter and $z_{uv}$ equals $1$ if vertex $v$ is in the set while vertex $u$ is not a member of the minimum set.

So, $x$ is variable controling the vertices while $z$ controls the edges.

I hope you can help me with modeling the second constraint.

I’m confused about the interaction between if nodes are decided to be in the set (i.e., $x_v = 1$) and the edge connected to it. P.S the edges are defined as $e=(u,v)$ where $u,v$ are the vertices incident to that edge.

Thank you so much in advance.

Answer 1

You can use the following model on the graph $G=(V,E)$: $$ \min \quad \sum_{v\in V} x_v $$ subject to \begin{align} x_u + x_v &\ge 1 \quad &\forall (u,v) \in E \\ \sum_{(u,v)\in E} z_{uv} &\ge k \\ z_{uv} &\le x_v \quad &\forall (u,v) \in E\\ z_{uv} &\le 1-x_u \quad &\forall (u,v) \in E\\ x_v&\in \{0,1\} \quad &\forall v \in V\\ z_{uv} &\in \{0,1\}\quad &\forall (u,v) \in E \end{align}

I believe your question specifically refers to the following constraints:

• $z_{uv} \le x_v \quad \forall (u,v) \in E$ : ensures that when $z_{uv}$ takes value $1$, vertex $v$ is selected and
• $z_{uv} \le 1-x_u \quad \forall (u,v) \in E$ : ensures that when $z_{uv}$ takes value $1$, vertex $u$ is left out