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
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
- Check out pulp's examples to understand the syntax
- 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$– AmedeoNov 1, 2020 at 0:19
-
$\begingroup$ Please help here (or.stackexchange.com/questions/5147/…) in re here (math.stackexchange.com/questions/1095760/…) $\endgroup$– BCLCNov 4, 2020 at 8:09
-
-
-