RelaxIV

RELAX-IV: A faster version of the RELAX code for solving minimum cost flow problems. The structure of dual ascent methods is particularly well-suited for taking advantage of good initial dual solutions of minimum cost flow problems. For this reason, these methods are extremely efficient for reoptimization and sensitivity analysis. In the absence of prior knowledge of a good initial dual solution, one may attempt to find such a solution by means of a heuristic initialization. RELAX-IV is a minimum cost flow code that combines the RELAX code of [BeT88a], [BeT88b] with an initialization based on a recently proposed auction/sequential shortest path algorithm. This initialization is shown to be extremely helpful in speeding up the solution of difficult problems, involving for example long augmenting paths, for which the relaxation method has been known to be slow. On the other hand, this initialization procedure does not significantly deteriorate the performance of the relaxation method for the types of problems where it has been known to be very fast. (Source: http://plato.asu.edu)


References in zbMATH (referenced in 20 articles )

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

  1. Kovács, Péter: Minimum-cost flow algorithms: an experimental evaluation (2015)
  2. Meyr, Herbert; Mann, Matthias: A decomposition approach for the general lotsizing and scheduling problem for parallel production lines (2013)
  3. Correia, Isabel; Lourenço, Lídia Lampreia; Saldanha-da-Gama, Francisco: Project scheduling with flexible resources: formulation and inequalities (2012)
  4. Geranis, George; Paparrizos, Konstantinos; Sifaleras, Angelo: On a dual network exterior point simplex type algorithm and its computational behavior (2012)
  5. Gopalakrishnan, Balaji; Kong, Seunghyun; Barnes, Earl; Johnson, Ellis L.; Sokol, Joel S.: A least-squares minimum-cost network flow algorithm (2011)
  6. Paparrizos, Konstantinos; Samaras, Nikolaos; Sifaleras, Angelo: An exterior simplex type algorithm for the minimum cost network flow problem (2009)
  7. Batenburg, Kees Joost: A network flow algorithm for reconstructing binary images from continuous x-rays (2008)
  8. Batenburg, K.J.: Network flow algorithms for discrete tomography (2007)
  9. Batenburg, Kees Joost: A network flow algorithm for binary image reconstruction from few projections (2006)
  10. Nonobe, Koji; Ibaraki, Toshihide: A metaheuristic approach to the resource constrained project scheduling with variable activity durations and convex cost functions (2006)
  11. Batenburg, K.J.: An evolutionary algorithm for discrete tomography (2005)
  12. Hansen, Ben B.: Full matching in an observational study of coaching for the sat (2004)
  13. Correia, Isabel; Captivo, M. Eugénia: A Lagrangean heuristic for a modular capacitated location problem (2003)
  14. Brunetta, Lorenzo; Conforti, Michele; Fischetti, Matteo: A polyhedral approach to an integer multicommodity flow problem (2000)
  15. Bertsekas, D.P.: Network optimization: continuous and discrete models (1998)
  16. Fuchssteiner, B.; Morisse, K.: Infinite networks: Minimal cost flows (1996)
  17. Mehrotra, Sanjay; Wang, Jen-Shan: Conjugate gradient based implementation of interior point methods for network flow problems (1996)
  18. Morisse, Karsten: Minimal cost flows in finite and infinite networks (1996)
  19. Bertsekas, Dimitri P.; Tseng, Paul: Relaxation methods for minimum cost ordinary and generalized network flow problems (1988)
  20. Tseng, Paul; Bertsekas, Dimitri P.: Relaxation methods for linear programs (1987)