Originally posted by: JimDan

I wrote a primal network simplex code using some of the tried-and-tested ideas in this area (series of papers by Barr, Glover and Klingman. Linear Programming and Network Flows - Bazaara, Jarvis and Sherali). The main claim of such codes is that for network problems such codes are faster (some papers claim anywhere from 10-100 times faster) than the primal simplex algorithm. However, I am unable to observe/replicate such results. That is, I have a network flow problem formulated as a min-cost-flow problem. I provide the same problem to my primal network simplex code on the one hand, and to the primal simplex algorithm (turn off all preprocessing, other parameters default) of CPLEX 12.2. Yet, the latter beats my primal network simplex code handsomely in terms of computational time.

It is possible my primal network simplex code is suboptimal in the sense that I may be using the wrong C++ data structures. For instance, I simply use node-length integer arrays to store the network simplex data structures.

int predecessor[NODE_LENGTH];
int depth[NODE_LENGTH];
int thread[NODE_LENGTH];

Is this the best possible way to represent the basis tree? Or are there any better representations?

I am curious to know how the network-simplex code inside of CPLEX is coded - ie. what datastructures are used...integer arrays or some sort of std::vector-type data structures?

Can any of the CPLEX developers share some type of recent summary results of network problems that they solve using ordinary primal simplex and the network simplex?

Thanks.

PS: I start my network simplex algorithm using the Big-M method while CPLEX probably proceeds via Phase 1-Phase 2 method. This will cause a difference in the number of iterations, but the difference is too small to explain the rather large gap in the computational times.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I think the data structure inside CPLEX is kind of a commercial secrete... You will probably not get the answer here...

For the commercial computational software, the designers will have some state-of-the-art techniques in the numerical computations. So it is not surprising that even your algorithm should theoretically beat the simplex method, but in practice, it is beaten by well-designed simplex method code. I think you could code the simplex method by yourself using the same data structure, then compare the computation time.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: JimDan

You are probably correct...I am still hoping, though, that some pointers can be made available for the research/academic community. All of us do sign an agreement before downloading and installing the academic version that it will not be used for commercial purposes.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

There are two things I think you should consider. The first is that CPLEX is coded by professionals, who I am sure have spent a fair bit of time tuning and optimizing their code. I can't speak for you, but I know the limits of my coding skills, and I would not expect my code to compete very well with CPLEX.

The second is the dates of the work you cited. I'm not positive, but I'm pretty sure that the assertions of 10x to 100x speed improvement over primal simplex date back a decade or two. Over that time frame, simplex codes have gotten a lot smarter about handling sparsity (one common characteristic of network problems) and doing basis updates. Are there are recent results claiming those sorts of speed increases for network simplex?

Cheers,
Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: JimDan

Paul:

The following is from CPLEX Manual for V12.2 (CPLEX > User's Manual for CPLEX > Continuous optimization > Solving network-flow problems > Choosing an optimizer: network considerations): "On a pure network problem, performance has been measured as 100 times faster with the network optimizer." Clearly CPLEX's simplex optimizer (being state-of-the-art) would exploit the numerical efficiencies that you mention to make the simplex algorithm run as fast as possible. Yet, somehow, (as the manual suggests), a performance improvement to the tune of 100x is still possible on using the primal network simplex. While I am sure that there is literature (in the last 30 years) dealing with sparse matrices and how the ordinary simplex algorithm can exploit it, it seems that there has not been any commensurate breakthrough (atleast that I am aware of) on making the primal network simplex algorithm more efficient.

Yet 10x-100x improvements have persisted in literature dating back 3-4 decades as well as now (going by the CPLEX manual). I am just scratching my head about the source of such improvements (given that ordinary simplex has benefited from fundamental advances mentioned above, while network simplex has not.) Is everything due to coding skill/efficiencies and coding optimization alone?

My coding skills are pretty ordinary...I (like you, may be) use coding as a tool to just get by.

Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> JimDan wrote:
> The following is from CPLEX Manual for V12.2 (CPLEX > User's Manual for CPLEX > Continuous optimization > Solving network-flow problems > Choosing an optimizer: network considerations): "On a pure network problem, performance has been measured as 100 times faster with the network optimizer."

Interesting. I confess I'm surprised the difference remains that large.

> Yet 10x-100x improvements have persisted in literature dating back 3-4 decades as well as now (going by the CPLEX manual). I am just scratching my head about the source of such improvements (given that ordinary simplex has benefited from fundamental advances mentioned above, while network simplex has not.) Is everything due to coding skill/efficiencies and coding optimization alone?

Well, I suspect that network simplex may also have benefited from improvements in the handling of sparse matrices. The other thing to keep in mind is that, IIRC, network simplex uses only addition and subtraction. Prior to the era of floating point processors, multiplication and division were much more expensive in CPU cycles than were addition and subtraction. It's tough to make a blanket statement like that any more when you have dedicated floating point processors with multiple registers -- here's an interesting thread about that -- but I think that divisions are still fairly expensive. Googling around, I found some charts that seem to indicate that on Intel i86 type chips the FDIV (floating point divide) operation at double precision has a latency at least 6 times longer than that of FSUB (floating subtract). That still doesn't get us anywhere near 100x, but if what passes for a basis update in network simplex takes a lot fewer operations than a pivot in primal simplex, we may have at least a partial explanation for the continued performance gap.
>
> My coding skills are pretty ordinary...I (like you, may be) use coding as a tool to just get by.

Indeed ... and I barely get by at that. :-)

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization