A computational study of cost reoptimization for min-cost flow problems. In the last two decades, a number of algorithms for the linear single-commodity min-cost flow (MCF) problem have been proposed, and several efficient codes are available that implement different variants of the algorithms. The practical significance of the algorithms has been tested by comparing the time required by their implementations for solving “from-scratch” instances of MCF, of different classes, as the size of the problem (number of nodes and arcs) increases. However, in many applications several closely related instances of MCF have to be sequentially solved, so that reoptimization techniques can be used to speed up computations, and the most attractive algorithm is the one that minimizes the total time required to solve all the instances in the sequence. In this paper we compare the performances of four different efficient implementations of algorithms for MCF under cost reoptimization in the context of decomposition algorithms for the multicommodity min-cost flow (MMCF) problem, showing that for some classes of instances the relative performances of the codes doing “from-scratch” optimization do not accurately predict the relative performances when reoptimization is used. Because the best solver depends both on the class and on the size of the instance, this work also shows the usefulness of a standard interface for MCF problem solvers that we have proposed and implemented. (Source:

References in zbMATH (referenced in 11 articles , 1 standard article )

Showing results 1 to 11 of 11.
Sorted by year (citations)

  1. Schieber, Baruch; Shachnai, Hadas; Tamir, Gal; Tamir, Tami: A theory and algorithms for combinatorial reoptimization (2018)
  2. Frangioni, Antonio; Gendron, Bernard; Gorgone, Enrico: On the computational efficiency of subgradient methods: a case study with Lagrangian bounds (2017)
  3. Frangioni, Antonio; Gorgone, Enrico: A library for continuous convex separable quadratic knapsack problems (2013)
  4. Gopalakrishnan, Balaji; Kong, Seunghyun; Barnes, Earl; Johnson, Ellis L.; Sokol, Joel S.: A least-squares minimum-cost network flow algorithm (2011)
  5. Coleman, Todd P.; Sarma, Sridevi S.: A computationally efficient method for nonparametric modeling of neural spiking activity with point processes (2010)
  6. Miller-Hooks, Elise; Tang, Hao; Chen, Zhiying: Updating network flows given multiple, heterogeneous arc attribute changes (2010)
  7. Altner, Doug; Ergun, Özlem: Rapidly solving an online sequence of maximum flow problems with extensions to computing robust minimum cuts (2008)
  8. Frangioni, A.; Gentile, C.: Prim-based support-graph preconditioners for min-cost flow problems (2007)
  9. Frangioni, Antonio; Manca, Antonio: A computational study of cost reoptimization for min-cost flow problems (2006)
  10. Batenburg, K. J.: An evolutionary algorithm for discrete tomography (2005)
  11. Boros, E.; Elbassioni, K.; Gurvich, V.; Khachiyan, L.: Enumerating minimal dicuts and strongly connected subgraphs and related geometric problems (2004)