# Is the order of edges in graph is changing the optimization result?

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)]

#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

• performance variability: or.stackexchange.com/questions/3419/… – RobPratt Nov 16 '20 at 22:17
• Thank you for your reply. I think the answer there is not directly related to my question. Since in my case changing the order of the graph edges, entry is controllable or as I think. Moreover, changing the order of the edges results in an expected output. – Amedeo Nov 17 '20 at 11:58

EDIT 1

I was able to replicate the issue and it turns out:

1. There is a problem in the objective function. You can only have $$1$$, while you have a loop. Replace your objective function by prob += lpSum(y)-lpSum(x). Maybe the confusion came from the fact that with lpSum, if your coefficients are $$1$$, you don't have to write the variables as a dictionnary with the indexes. But even after fixing this, the issue is still there.
2. If you take a look at the .lp files (print(prob)), you will see that both models are not the same. For example in one case, you have a variable x[(1,3)], and in the other case you have x[(3,1)]. And so this messes up the constraints $$x_{uv}\le y_u$$ and $$x_{uv}\le 1-y_v$$. This is because networkx created the edges differently in the first place.

So this issue is not related to optimization, or to a solver, it is due to the way the edges are defined. It seems you are working with an undirected graph, but have constraints where order matters. I am not sure there is enough information in the question to validate that. You may need to rethink your model.

If I understood correctly, you want all possible optimal solutions.

You can achieve this by iteratively solving the problem, adding a constraint at each iteration so that the next solution is different. If $$B$$ denotes the set of binaries that take value $$1$$ in the solution, you can add the following constraint : $$\sum_{i\in B}x_i \le |B| -1$$

This way, among all binaries that took value $$1$$, you impose that at least one has to take value $$0$$ this time.

Here is a possible python code:

while True:
prob.solve()
if LpStatus[prob.status] == "Optimal":

# display solution
S = 0
for v in g.nodes():
if pulp.value(y[v]) ==1:
print("node %s selected"%v)
S += 1
for (u,v) in g.edges():
if pulp.value(x[(u,v)]) ==1:
print("edge %s was included"%{(u,v)})

# Add the following constraint to preclude the solver from finding the same set of nodes in next iteration
prob += lpSum([y[v] for v in y if value(y[v])>0.9]) <= S -1

# If a new optimal solution cannot be found, we end the program
else:
break
• Thank you so much @Kuifje, I always really appreciate your answers. Sorry if I didn't clarify my point. In each scenario (i.e. a certain order of the edges) one optimal solution is obtained, there are no chances for other solutions. If we change the order of sorting the edges (for the same set of edges), a different sub-optimal solution is obtained. for my understanding, there is an optimal solution which should be unique whatever the order of the edges since it is defining the same graph. – Amedeo Nov 17 '20 at 14:50
• No problem, happy to help. How do you know the second solution is sub-optimal ? $\{5,4\}$ and $\{2,1\}$ both have objective value $2-1 =1$. Am I missing something ? – Kuifje Nov 17 '20 at 14:55
• I meant by sub-optimal that the given solution is not the minimum set vertices that satisfying the problem constraints and it is more dependent on the order of the set of edges. for example in the second scenario, if the order of the set of edges is [3,1,2,4,5], the solution will be {3,1,2} and so on. – Amedeo Nov 17 '20 at 15:12
• For the solver, I believe both solutions are optimal. If the second subset is sub-obtimal for some reason, it has to appear somehow in the model. If you have another example where the subset has a different objective value, then there is an issue indeed. Otherwise, I don't see a problem. – Kuifje Nov 17 '20 at 15:15
• I will give this example, if the set of edges is entered liks this edges = [(3,1),(4,1),(5,1),(4,2),(5,2),(1,2),(3,2)] the objective is 0 and the solution is the set of nodes {3,1,4,5}. IF i just moved the link (1,2) to be at the biegining of the set , the order of the nodes then will be {1,2,3,4,5}, and the solution is the set of nodes {1,2} with 6 edges have been included , so the objective is -2 while it is the same set of edges in both cases – Amedeo Nov 17 '20 at 15:24