Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems

Tibor Illes, Richárd Molnár-Szipai

Research output: Book/ReportOther report

Abstract

The maximum flow problem (MFP) is a fundamental model in operations research. The network simplex algorithm is one of the most efficient solution methods for MFP in practice. The theoretical properties of established pivot algorithms for MFP is less understood. Variants of the primal simplex and dual simplex methods for MFP have been proven strongly polynomial, but no similar result exists for other pivot algorithms like the monotonic build-up or the criss-cross simplex algorithm. The monotonic build-up simplex algorithm (MBUSA) starts with a feasible solution, and fixes the dual feasibility one variable a time, temporarily losing primal feasibility. In the case of maximum flow problems, pivots in one such iteration are all dual degenerate, bar the last one. Using a labelling technique to break these ties we show a variant that solves the maximum flow problem in 2|V||A|2 pivots.
LanguageEnglish
Number of pages16
Volume2015
Publication statusPublished - 1 Sep 2015

Publication series

NameOperations Research Report
PublisherELTE
ISSN (Print)1215-5918

Fingerprint

Polynomials
Labeling
Simplex method
Operations research

Keywords

  • maximum flow problem
  • pivot algorithm
  • monotonic build-up simplex algorithm

Cite this

Illes, T., & Molnár-Szipai, R. (2015). Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems. (Operations Research Report).
Illes, Tibor ; Molnár-Szipai, Richárd. / Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems. 2015. 16 p. (Operations Research Report).
@book{78769f3e436f4e8392e1691232bcaddb,
title = "Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems",
abstract = "The maximum flow problem (MFP) is a fundamental model in operations research. The network simplex algorithm is one of the most efficient solution methods for MFP in practice. The theoretical properties of established pivot algorithms for MFP is less understood. Variants of the primal simplex and dual simplex methods for MFP have been proven strongly polynomial, but no similar result exists for other pivot algorithms like the monotonic build-up or the criss-cross simplex algorithm. The monotonic build-up simplex algorithm (MBUSA) starts with a feasible solution, and fixes the dual feasibility one variable a time, temporarily losing primal feasibility. In the case of maximum flow problems, pivots in one such iteration are all dual degenerate, bar the last one. Using a labelling technique to break these ties we show a variant that solves the maximum flow problem in 2|V||A|2 pivots.",
keywords = "maximum flow problem, pivot algorithm, monotonic build-up simplex algorithm",
author = "Tibor Illes and Rich{\'a}rd Moln{\'a}r-Szipai",
year = "2015",
month = "9",
day = "1",
language = "English",
volume = "2015",
series = "Operations Research Report",
publisher = "ELTE",

}

Illes, T & Molnár-Szipai, R 2015, Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems. Operations Research Report, vol. 2015.

Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems. / Illes, Tibor; Molnár-Szipai, Richárd.

2015. 16 p. (Operations Research Report).

Research output: Book/ReportOther report

TY - BOOK

T1 - Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems

AU - Illes, Tibor

AU - Molnár-Szipai, Richárd

PY - 2015/9/1

Y1 - 2015/9/1

N2 - The maximum flow problem (MFP) is a fundamental model in operations research. The network simplex algorithm is one of the most efficient solution methods for MFP in practice. The theoretical properties of established pivot algorithms for MFP is less understood. Variants of the primal simplex and dual simplex methods for MFP have been proven strongly polynomial, but no similar result exists for other pivot algorithms like the monotonic build-up or the criss-cross simplex algorithm. The monotonic build-up simplex algorithm (MBUSA) starts with a feasible solution, and fixes the dual feasibility one variable a time, temporarily losing primal feasibility. In the case of maximum flow problems, pivots in one such iteration are all dual degenerate, bar the last one. Using a labelling technique to break these ties we show a variant that solves the maximum flow problem in 2|V||A|2 pivots.

AB - The maximum flow problem (MFP) is a fundamental model in operations research. The network simplex algorithm is one of the most efficient solution methods for MFP in practice. The theoretical properties of established pivot algorithms for MFP is less understood. Variants of the primal simplex and dual simplex methods for MFP have been proven strongly polynomial, but no similar result exists for other pivot algorithms like the monotonic build-up or the criss-cross simplex algorithm. The monotonic build-up simplex algorithm (MBUSA) starts with a feasible solution, and fixes the dual feasibility one variable a time, temporarily losing primal feasibility. In the case of maximum flow problems, pivots in one such iteration are all dual degenerate, bar the last one. Using a labelling technique to break these ties we show a variant that solves the maximum flow problem in 2|V||A|2 pivots.

KW - maximum flow problem

KW - pivot algorithm

KW - monotonic build-up simplex algorithm

UR - http://www.cs.elte.hu/opres/orr/download/ORR_2015_02.pdf

M3 - Other report

VL - 2015

T3 - Operations Research Report

BT - Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems

ER -

Illes T, Molnár-Szipai R. Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems. 2015. 16 p. (Operations Research Report).