Inquiry Regarding Gurobi's Recent Improvements in Network Simplex Algorithm

Ongoing

Li zheng

November 09, 2023 10:11

• 
• 

Dear Gurobi Team,

I am a current undergraduate student conducting research in the field of minimum cost flow algorithms. In my recent work, I have been focusing on the optimization of solving linear programs with network structure, particularly in the context of minimum cost flow problems.

I have noticed that the latest version of Gurobi has introduced a "New network simplex algorithm" which claims to greatly speed up the solution of linear programs with network structure. As such, I am writing to inquire whether there are any recent academic publications or technical reports documenting the improvements Gurobi has made in the network simplex algorithm, or any related references that I could leverage in my research.

I have conducted a thorough literature review but have not come across specific details regarding Gurobi's enhancements in the area of network simplex algorithm. Therefore, I would greatly appreciate any information or pointers to relevant literature that could provide insights into these developments.

I believe that understanding and incorporating these advancements into my research could significantly benefit my work and contribute to the advancement of optimization techniques for network-related problems.

Thank you for your attention to this matter. I look forward to any guidance or resources that you may be able to provide.

Sincerely,

Lizheng

Related to

• Networks

0

• 

  David Torres Sanchez

  • Gurobi Staff

  November 23, 2023 10:16

  Hi Lizheng,

  We do not have any specific references regarding our implementation.

  There are, however, some recent papers on this topic where you can find details of state-of-the-art implementations (not just the network simplex but also other algorithms):

  • Kovács, P. (2015). Minimum-cost flow algorithms: an experimental evaluation. Optimization Methods and Software, 30(1), 94-127. Test suite, docs, source code.

  Cheers, 
  David

  0
• 

  OneCable OneCable

  December 15, 2024 00:12 Edited

  • 
  • 

  Hi David, 

  I have a follow-up to this. When it is stated that Gurobi implements the network simplex algorithm, does this mean that there is a C API which directly allows the user to input the nodes, arcs, lower/upper bounds on arcs, costs, and the supplies/demands at various nodes without explicitly formulating the network problem as a linear program?

  Or, does it mean that the user has to enter a traditional linear program with only at most one +1 and one -1 in a column and then Gurobi will "intelligently" recognize this as a network problem and solve it using the network simplex algorithm? That is, behind the scenes, Gurobi will create nodes (corresponding to constraints) and arcs (corresponding to columns) and then create a basis tree, pivot using an entering arc, find out the leaving arc, etc.

  I ask this for two reasons:

  (a) Going through the documentation, here, and your answer from here, it appears that the user has to indeed formulate it as a traditional linear program and request Gurobi to solve it by invoking the network simplex.

  (b) CPLEX offers a C API where the LP does not need to be formulated but instead the user can directly specify the arcs, costs, supplies, demands, etc. and invoke the network simplex. Please see here.

  Lastly, are there query/control callbacks available to the user to query/control the various steps of the network simplex iterations -- query the currently chosen entering arc, current basis tree, currently chosen exitting arc, etc.

  Thanks.

  0
• 

  David Torres Sanchez

  • Gurobi Staff

  December 16, 2024 15:16 Edited

  Hi,

  Or, does it mean that the user has to enter a traditional linear program with only at most one +1 and one -1 in a column and then Gurobi will "intelligently" recognize this as a network problem and solve it using the network simplex algorithm? That is, behind the scenes, Gurobi will create nodes (corresponding to constraints) and arcs (corresponding to columns) and then create a basis tree, pivot using an entering arc, find out the leaving arc, etc.

  This option. We automatically detect the structure, additionally, you will have to set the parameter NetworkAlg=1 to enable network simplex.

  (b) CPLEX offers a C API where the LP does not need to be formulated but instead the user can directly specify the arcs, costs, supplies, demands, etc. and invoke the network simplex. Please see here.

  Would this be interesting for you? I can create a feature request, similarly for the callback options as these are not available. I'm not sure this will be implemented, if you want this level of customisation I suggest you look into open source network simplex implementations.

  Cheers, 
  David

   

  1

Please sign in to leave a comment.