DOI: 10.1287/opre.36.1.93. Relaxation Methods for Minimum Cost Ordinary and Generalized Network Flow Problems

Relaxation Methods for Minimum Cost Ordinary and Generalized Network Flow Problems

10.1287/opre.36.1.93

Crossref journal-article

Institute for Operations Research and the Management Sciences (INFORMS)

Operations Research (109)

Abstract

We propose a new class of algorithms for linear cost network flow problems with and without gains. These algorithms are based on iterative improvement of a dual cost and operate in a manner that is reminiscent of coordinate ascent and Gauss-Seidel relaxation methods. We compare our coded implementations of these methods with mature state-of-the-art primal simplex and primal-dual codes, and find them to be several times faster on standard benchmark problems, and faster by an order of magnitude on large, randomly generated problems. Our experiments indicate that the speedup factor increases with problem dimension.

Bibliography

Bertsekas, D. P., & Tseng, P. (1988). Relaxation Methods for Minimum Cost Ordinary and Generalized Network Flow Problems. Operations Research, 36(1), 93â114.

Authors 2

Dimitri P. Bertsekas (first)
Paul Tseng (additional)

References 0 Referenced 121

None

Dates

Type	When
Created	16 years, 9 months ago (Nov. 8, 2008, 8:45 a.m.)
Deposited	2 years, 4 months ago (April 2, 2023, 9:27 a.m.)
Indexed	1 month, 1 week ago (July 13, 2025, 10:45 p.m.)
Issued	37 years, 6 months ago (Feb. 1, 1988)
Published	37 years, 6 months ago (Feb. 1, 1988)
Published Print	37 years, 6 months ago (Feb. 1, 1988)

Funders 0

None

BibTeX

@article{Bertsekas_1988, title={Relaxation Methods for Minimum Cost Ordinary and Generalized Network Flow Problems}, volume={36}, ISSN={1526-5463}, url={http://dx.doi.org/10.1287/opre.36.1.93}, DOI={10.1287/opre.36.1.93}, number={1}, journal={Operations Research}, publisher={Institute for Operations Research and the Management Sciences (INFORMS)}, author={Bertsekas, Dimitri P. and Tseng, Paul}, year={1988}, month=feb, pages={93–114} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        7,
        14
      ]
    ],
    "date-time": "2025-07-14T02:45:51Z",
    "timestamp": 1752461151265
  },
  "reference-count": 0,
  "publisher": "Institute for Operations Research and the Management Sciences (INFORMS)",
  "issue": "1",
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        1988,
        2
      ]
    ]
  },
  "abstract": "<jats:p> We propose a new class of algorithms for linear cost network flow problems with and without gains. These algorithms are based on iterative improvement of a dual cost and operate in a manner that is reminiscent of coordinate ascent and Gauss-Seidel relaxation methods. We compare our coded implementations of these methods with mature state-of-the-art primal simplex and primal-dual codes, and find them to be several times faster on standard benchmark problems, and faster by an order of magnitude on large, randomly generated problems. Our experiments indicate that the speedup factor increases with problem dimension. </jats:p>",
  "DOI": "10.1287/opre.36.1.93",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2008,
        11,
        8
      ]
    ],
    "date-time": "2008-11-08T13:45:52Z",
    "timestamp": 1226151952000
  },
  "page": "93-114",
  "source": "Crossref",
  "is-referenced-by-count": 121,
  "title": "Relaxation Methods for Minimum Cost Ordinary and Generalized Network Flow Problems",
  "prefix": "10.1287",
  "volume": "36",
  "author": [
    {
      "given": "Dimitri P.",
      "family": "Bertsekas",
      "sequence": "first",
      "affiliation": [
        {
          "name": "Massachusetts Institute of Technology, Cambridge, Massachusetts"
        }
      ]
    },
    {
      "given": "Paul",
      "family": "Tseng",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Massachusetts Institute of Technology, Cambridge, Massachusetts"
        }
      ]
    }
  ],
  "member": "109",
  "container-title": "Operations Research",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://pubsonline.informs.org/doi/pdf/10.1287/opre.36.1.93",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2023,
        4,
        2
      ]
    ],
    "date-time": "2023-04-02T13:27:18Z",
    "timestamp": 1680442038000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://pubsonline.informs.org/doi/10.1287/opre.36.1.93"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        1988,
        2
      ]
    ]
  },
  "references-count": 0,
  "journal-issue": {
    "issue": "1",
    "published-print": {
      "date-parts": [
        [
          1988,
          2
        ]
      ]
    }
  },
  "alternative-id": [
    "10.1287/opre.36.1.93"
  ],
  "URL": "http://dx.doi.org/10.1287/opre.36.1.93",
  "relation": {},
  "ISSN": [
    "0030-364X",
    "1526-5463"
  ],
  "subject": [],
  "container-title-short": "Operations Research",
  "published": {
    "date-parts": [
      [
        1988,
        2
      ]
    ]
  }
}