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

Question

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

Answer 1

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.

---

INITIAL ANSWER

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