Experiments with "extended crossover" approaches for network flow problems

Interior Point algorithms for Min-Cost Flow problems have been shown to be competitive with more established "combinatorial" approaches, at least on some problem classes and for very large instances. A fundamental contribution to the efficiency of these approaches is provided by the specialized crossover routines that can be implemented for this problem; they allow early termination of the IP approach, sparing it with the "nasty" iterations where the core linear systems become very difficult to solve by iterative algorithms. Because crossover procedures are nothing but one step of a combinatorial approach to MCF, we propose to extend this concept to that of extended crossover: use the initial part of an Interior Point algorithm to MCF to warm-start a "combinatorial" algorithm. We report our experiments along this line using, as "combinatorial companion", a primal-dual algorithm for MCF that has a natural way for exploiting the information provided by the IP approach. Our results show that the efficiency of the combined approach critically depends on the accurate selection of a set of parameters among very many possible ones, for which designing accurate guidelines appears not to be an easy task; however, they also show that the combined approach can be competitive with the two original approaches in isolation, at least on some "difficult" instances.