The hypergraph simplex approach: some experimental results

We consider the Hypergraph Simplex approach recently proposed for the Minimum Cost Hyperflow Problem, and report the results of a wide computational experimentation aimed to investigate the practical efficiency of the approach. In our experimentation, we have considered both random hypergraphs and hypergraphs having some particular structures. In the case of random hypergraphs, a comparison with one of the best state-of-the-art LP codes, i.e. CPLEX, has been performed. The results are rather interesting: as the size and the density of the instances increase, our implementation is faster than CPLEX. In the other cases, the two programs are competitive. In the second case, we have chosen the Multicommodity Flow Problem as a case study, and run a set of test instances obtained from C.R.T. of Montreal. We have compared our results with both primal and dual versions of CPLEX, and with an ‘ad hoc’ dual code, named MMCFB, which is based on cost decomposition and uses bundle techniques for solving the Lagrangean dual. Also in this case the Hypergraph Simplex implementation has shown a stable behaviour, and its running time is in general in the middle with respect to that of CPLEX and of MMCFB.