4
$\begingroup$

As a following up for my question for modeling a simple moded of the minimum set vertex cover problem, which is shown next. I would like to have your help in modeling this problem using Python or MATLAB. I believe that each edge with its origin vertex and destination vertex as a binary variable will solve the problem. I'm a little confused about how this variable will represent both vertices.
The problem can be shown as graph $G=(V,E)$ where we want to: $$ \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}

$\endgroup$
6
$\begingroup$

In Python, with pulp and networkx :

import pulp 
import networkx as nx

G = nx.Graph()
# define your graph here
#...


# define the problem
prob = pulp.LpProblem("MinimumSetVertexCover", pulp.LpMinimize)

# define the variables
x = pulp.LpVariable.dicts("x", G.nodes(), cat=pulp.LpBinary)
z = pulp.LpVariable.dicts("z", G.edges(), cat=pulp.LpBinary)

# define the objective function
prob += pulp.lpSum(x)

# define the constraints
for (u,v) in G.edges():
    prob += x[u] + x[v] >= 1
    prob += z[(u,v)] <= x[v]
    prob += z[(u,v)] <= 1-x[u]
prob += pulp.lpSum(z) >= k

# solve
prob.solve()

# display objective function value
print("number of vertices in solution : %s"%pulp.prob.objective.value())

# display solution
for v in G.nodes():
    if pulp.value(x[v]) > 0.9:
         print("node %s selected"%v)

I suggest you

  1. Check out pulp's examples to understand the syntax
  2. Do not just copy paste the above answer if you want to learn something
$\endgroup$
5
  • 1
    $\begingroup$ Thank you so much for your help. I really appreciate your advice. $\endgroup$
    – Amedeo
    Nov 1 '20 at 0:19
  • $\begingroup$ Please help here (or.stackexchange.com/questions/5147/…) in re here (math.stackexchange.com/questions/1095760/…) $\endgroup$
    – BCLC
    Nov 4 '20 at 8:09
  • $\begingroup$ @Amedeo Kuifje helped me a lot before too. $\endgroup$
    – BCLC
    Nov 4 '20 at 8:10
  • $\begingroup$ Sorry but what is k? $\endgroup$
    – Marcel
    Nov 30 '20 at 14:23
  • $\begingroup$ A given parameter. $\endgroup$
    – Kuifje
    Nov 30 '20 at 14:29

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.