Originally posted by: JimDan

Hello,

If I understand correctly, the most efficient network simplex algorithm requires node length arrays to maintain and perform operations on the tree. 

In scanning the literature on what are the best data structures to implement network simplex, the augmented thread index list structures seems to come up. See for instance, (Linear Programming and Network Flows, Bazaraa, Jarvis and Sherali and Network Flows, Ahuja, Magnanti and Orlin). These list structures include: predecessor[], depth[], thread[], orient[] and flow[] and dual[], the latter two maintaining the primal flows on arcs and dual values associated with the nodes, while the former four help maintain the basis tree.

Could CPLEX developers clarify if this is indeed what is implemented in CPLEX network simplex optimizer? I am hoping this is not proprietary information. Could you point me to published literature which gives details of these structures and how they are to be updated from iteration to iteration?

It is just that I am encountering a large network problem which seems to have some additional specialized structure and I am currently developing an even more specialized algorithm than the primal network simplex to solve my problem and would like to eventually compare the computational times with the network optimizer.

Thanks.

Originally posted by: BoJensen

There are two standard approaches to store the network basis :

1) predecessor[], depth[], thread[], orient[] as you mention described in Network Flows, Ahuja, Magnanti and Orlin

2) subtreesize[], predecessor[], child[], leftsibling[], rightsibling[], basicarc[] see Andreas Löbel Solving Large-Scale Real-World Minimum-Cost Flow Problems by a Network Simplex Method (1996)

Personally I have had best experience by implementing 2) in the past (not in CPLEX), but both should be fast.

As a side note, I think the problems should be fairly large before using these techniques. Most network problems have a structure, which makes standard dual simplex perform well.

Originally posted by: JimDan

Bo,

I seem to have MCF-1.3 auhored by Andreas Lobel. It seems to be dated after 1996, so I am guessing it would be based off the 1996 paper. Would you happen to know if this is the latest version?

His website http://typo.zib.de/opt-long_projects/Software/Mcf/ does not load at my end. Perhaps I will try later.

Any chance you would know if CPLEX network optimizer implements (1) or (2)?

Thanks.

Originally posted by: BoJensen

You will have to ask Andreas Löbel, I do not use the software. Sorry but we do not comment on specific implementation details internally in CPLEX . I think you're good with the structures suggested above.