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?

  • 2
    $\begingroup$ 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 ? $\endgroup$
    – Kuifje
    Dec 5, 2020 at 17:57
  • $\begingroup$ 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? $\endgroup$
    – Amedeo
    Dec 5, 2020 at 18:07
  • $\begingroup$ 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. $\endgroup$
    – Kuifje
    Dec 5, 2020 at 18:34
  • $\begingroup$ All optimal solutions will have the same objective value (by definition of "optimal"). So what makes one optimal solution the "best" optimal solution? $\endgroup$
    – prubin
    Dec 5, 2020 at 20:09
  • $\begingroup$ 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. $\endgroup$
    – Amedeo
    Dec 5, 2020 at 21:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.