I am solving an optimization problem using Pulp and NetworkX. The problem is similar to the Minimum Vertex Set (MVS) problem. I have noticed that the optimizer is Scanning the edges according to their order in the entry of set edges and deciding about the minimum set according to that. In other words, the results are changing according to the order of the edges, for example, if I define the set of edges as
edges = [(5,4),(5,3),(3,1),(3,2),(2,1),(4,1),(5,1),(4,2),(5,2),(4,3)]
The order of nodes in this case is [5,4,3,1,2]
and the minimum set is {5,4}
while enring the set of edges as
edges = [(2,1),(2,3),(3,1),(4,1),(5,1),(4,2),(5,2),(4,3),(5,3),(5,4)]
The order of the nodes is [2,1,3,4,5]
and the minimum set is {2,1}
Is there a way to scan all the posibilites instead of going with the nodes one by one and ignoring the other nodes if the solution is satisfied.Here is the code I am using:
import pulp
import networkx as nx
import numpy as np
g = nx.Graph()
edges = [(1,2),(3,1),(4,1),(5,1),(4,2),(5,2),(3,2)]
#edges = [(3,1),(4,1),(5,1),(4,2),(5,2),(1,2),(3,2)]
g.add_edges_from(edges)
#The problem
prob = pulp.LpProblem("MinimumSetVertexCover", pulp.LpMinimize)
# The variables
y = pulp.LpVariable.dicts("y", g.nodes(), cat=pulp.LpBinary)
x = pulp.LpVariable.dicts("x", g.edges(), cat=pulp.LpBinary)
#The objective function
for (u,v) in g.edges():
prob += pulp.lpSum(y) - pulp.lpSum(x)
#The constraints
for (u,v) in g.edges():
prob += x[(u,v)] <= y[u]
prob += x[(u,v)] <= 1-y[v]
for v in g.nodes():
prob += pulp.lpSum([x[(u,v)] for u in g.neighbors(v) if (u,v) in x])+pulp.lpSum([x[(v,u)] for u in g.neighbors(v) if (v,u) in x]) >= 2*(1-y[v])
prob.solve()
for v in g.nodes():
if pulp.value(y[v]) ==1:
print("node %s selected"%v)
for (u,v) in g.edges():
if pulp.value(x[(u,v)]) ==1:
print("edge %s was included"%{(u,v)})
Thank you for helping me figuring this out