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

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .