Cycles in solutions from Network Simplex

進行中

Julian Maus

2025年08月24日 12:08

• 
• 

Hello everyone,

as part of my bachelor thesis, I have been studying the runtime of algorithms for computing acyclic flows in networks. One of the algorithms I looked at is the Network Simplex algorithm. According to the literature, it returns a spanning tree as a basis and should therefore produce acyclic solutions.

During my experiments, however, I noticed that Gurobi’s implementation of the Network Simplex algorithm sometimes produces solutions that contain cycles. On certain test instances, Gurobi even produced by far the most cycles compared to other solvers.

My questions are:

• Is this behavior intentional (e.g. due to implementation details or performance reasons)?
• Is there any documentation or explanation of this behavior?

Any insights would be very helpful for interpreting my results correctly.

Thanks a lot in advance!

Best,

Julian Maus

 

関連

• Simplex
• Networks

0

• 

  Matthias Miltenberger

  • Gurobi Staff

  2025年08月25日 10:55

  Hi Julian,

  Did you enable the Network Simplex explicitly when running your tests? You can do this by setting the parameter NetworkAlg to 1. Can you share more details about your test, please?

  Cheers,
  Matthias

  0
• 

  Julian Maus

  2025年08月26日 08:00

  • 
  • 

  Hello Matthias,

  As part of my bachelor thesis I compared different algorithms for computing maximum acyclic flows. I also considered algorithms that may produce cyclic maximum flows and in these cases applied a naive cycle elimination procedure.

  For testing, I used the instances published by Dr. Kovács (https://lemon.cs.elte.hu/trac/lemon/wiki/MinCostFlowData), which I adapted so that only maximum flows were computed. In this context I explicitly enabled the Network Simplex Algorithm in order to evaluate its performance.

  In the evaluation I observed that the Network Simplex Algorithm produced cycles very frequently and was therefore significantly slower than the other approaches, which was quite surprising to me. Further experiments suggested that this behavior is related to presolving. With presolving disabled, cycles still occurred but in much smaller numbers. Under these conditions, the Network Simplex Algorithm turned out to be among the most efficient algorithms, comparable to the Link Cut Trees.

  If of interest, I would be happy to share my code and the CSV outputs of my experiments.

  Best regards,
  Julian

  0

サインインしてコメントを残してください。