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$

1 Answer 1

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, 2020 at 13:46
  • 2
    $\begingroup$ Happy to help ! $\endgroup$
    – Kuifje
    Oct 30, 2020 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, 2020 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, 2020 at 16:41
  • $\begingroup$ Thank you so much @Kuifje. I will do that $\endgroup$
    – Amedeo
    Oct 31, 2020 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.