# MILP formulation for minimum set Vertex cover problem

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.

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}
• $$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