Algorithms for the problem of non-capacitated flows with fixed costs in arcs: a statistical comparison

This paper is concerned about empirical comparisons of algorithms, one of the most recurrent issues in the field of design of algorithms. The problem under consideration is the non-capacitated fixed-charge network flow (UFCNF) problem, a generalization of the classic Steiner problem in graphs. The UFCNF is very important in the practical point of view because of its potential applications for telecommunication and transportation system design. In order to compare the algorithms for the UFCNF problem, we make use of well known and well established statistical tools namely the design of experiments, analysis of variance, and confidence intervals, but rarely applied in such studies. A mixed-integer mathematical programming formulation is presented for the UFCNF problem.