2

I'm solving a network optimization problem which is modeled as a graph $G=(V,E)$. Solving this problem using Pulp and NetworkX in Python and ordering the graph's nodes in a certain order (i.e. (1,2,3,4,5)) gives a certain optimal solution. However, changing the order of the nodes (i.e.,(3,4,1,2,5)) may lead to another optimal solution. Is there a metric for nodes that can order the nodes to provide the best optimal solution/s instead of going through the whole possible orders?

Amedeo
  • 443
  • 3
  • 8
  • 2
    I see you are still struggling with this issue. I still think the problem should be solved at the root, and not at this stage. To me this looks like a consequence of an ill posed problem. I would suggest investigating from the very beginning and sharing your problem entirely, not just bits here and there. Also the initial context would help. Is this part of a research project ? an industrial project ? fun ? – Kuifje Dec 05 '20 at 17:57
  • Thank you Kuifje for your comment. Sure it is not for fun. I'm working on a research project. I have solved the problem to an optimal solution as I mentioned but I was curious regarding the ordering of the nodes since I've noticed it might change the optimal solution. So, I was curious to know if there is an optimal ordering for the nodes. Regarding posting questions and learning from others experience, isn't that what is it all about? – Amedeo Dec 05 '20 at 18:07
  • Yes of course this what this forum is all about, don't get me wrong :) It's just that this question hints that there may be a problem somewhere upstream. If changing the order of the nodes has an influence on the solution, then I would have little confidence in having reached optimality. – Kuifje Dec 05 '20 at 18:34
  • All optimal solutions will have the same objective value (by definition of "optimal"). So what makes one optimal solution the "best" optimal solution? – prubin Dec 05 '20 at 20:09
  • Thank you for your comment Kuifje. @prubin As I understand, each order of the nodes is considered as a different scenario, that is why each order getting a different solution and a different objective value. – Amedeo Dec 05 '20 at 21:05
  • @Amedeo Are you saying that the optimal value obtained using one ordering is different in objective value from the optimal solution obtained using another ordering, but that all orderings have the same underlying graph? – prubin Dec 05 '20 at 22:08
  • @prubin As I understand, indeed, the objective value changes. The initial thread was here – Kuifje Dec 05 '20 at 22:28

0 Answers0