7
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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
$\endgroup$
5
  • 1
    $\begingroup$ Thank you @Kuifje so much. I appreciate your help. $\endgroup$ – Amedeo Oct 30 '20 at 13:46
  • 2
    $\begingroup$ Happy to help ! $\endgroup$ – Kuifje Oct 30 '20 at 13:47
  • $\begingroup$ Dear @Kuifje, I would like to have your help in understanding how E as an edge that links two vertices (u,v) can be modeled to be expressed by z_uv has 1 or 0 and compared to variable x that has only v or u. In other words, I can't get that in Python or Matlab. Please help. $\endgroup$ – Amedeo Oct 31 '20 at 15:38
  • 1
    $\begingroup$ No problem I can show you the python code, just post it as a new question and i will answer there. $\endgroup$ – Kuifje Oct 31 '20 at 16:41
  • $\begingroup$ Thank you so much @Kuifje. I will do that $\endgroup$ – Amedeo Oct 31 '20 at 19:22

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.