# MILP Minimum set Vertex cover coding by Python or MATLAB?

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}

In Python, with pulp and networkx :

import pulp
import networkx as nx

G = nx.Graph()
#...

# 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
• Thank you so much for your help. I really appreciate your advice. Nov 1, 2020 at 0:19