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}


1 Answer 1


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

# 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
  • 1
    $\begingroup$ Thank you so much for your help. I really appreciate your advice. $\endgroup$
    – Amedeo
    Commented Nov 1, 2020 at 0:19
  • $\begingroup$ Please help here (or.stackexchange.com/questions/5147/…) in re here (math.stackexchange.com/questions/1095760/…) $\endgroup$
    – BCLC
    Commented Nov 4, 2020 at 8:09
  • $\begingroup$ @Amedeo Kuifje helped me a lot before too. $\endgroup$
    – BCLC
    Commented Nov 4, 2020 at 8:10
  • $\begingroup$ Sorry but what is k? $\endgroup$
    – Marcel
    Commented Nov 30, 2020 at 14:23
  • $\begingroup$ A given parameter. $\endgroup$
    – Kuifje
    Commented Nov 30, 2020 at 14:29

Your Answer

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

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