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

Tibor Illés, Molnár-Szipai Richárd

Research output: Contribution to journalArticle

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 are 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 (MBU SA) starts with a feasible solution, and fixes the dual feasibility one variable at 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||E|2 pivots.
LanguageEnglish
Pages201-210
Number of pages10
JournalDiscrete Applied Mathematics
Volume214
Early online date22 Jul 2016
DOIs
Publication statusPublished - 11 Dec 2016

Fingerprint

Simplex Algorithm
Maximum Flow
Monotonic
Pivot
Polynomials
Polynomial
Operations research
Dual Method
Simplex Method
Labeling
Operations Research
Network Algorithms
Tie
Efficient Solution
Iteration

Keywords

  • maximum flow problem
  • pivot algorithms
  • MBU algorithm
  • operations research
  • polynomial
  • simplex algorithms
  • labelling technique

Cite this

Illés, Tibor ; Richárd, Molnár-Szipai. / Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems. In: Discrete Applied Mathematics. 2016 ; Vol. 214. pp. 201-210.
@article{04e203ad562a42f68a4b0ca98f24a638,
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 are 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 (MBU SA) starts with a feasible solution, and fixes the dual feasibility one variable at 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||E|2 pivots.",
keywords = "maximum flow problem, pivot algorithms, MBU algorithm, operations research, polynomial, simplex algorithms, labelling technique",
author = "Tibor Ill{\'e}s and Moln{\'a}r-Szipai Rich{\'a}rd",
year = "2016",
month = "12",
day = "11",
doi = "10.1016/j.dam.2016.06.026",
language = "English",
volume = "214",
pages = "201--210",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",

}

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

In: Discrete Applied Mathematics, Vol. 214, 11.12.2016, p. 201-210.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Illés, Tibor

AU - Richárd, Molnár-Szipai

PY - 2016/12/11

Y1 - 2016/12/11

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 are 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 (MBU SA) starts with a feasible solution, and fixes the dual feasibility one variable at 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||E|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 are 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 (MBU SA) starts with a feasible solution, and fixes the dual feasibility one variable at 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||E|2 pivots.

KW - maximum flow problem

KW - pivot algorithms

KW - MBU algorithm

KW - operations research

KW - polynomial

KW - simplex algorithms

KW - labelling technique

UR - http://www.sciencedirect.com/science/article/pii/S0166218X16303055

U2 - 10.1016/j.dam.2016.06.026

DO - 10.1016/j.dam.2016.06.026

M3 - Article

VL - 214

SP - 201

EP - 210

JO - Discrete Applied Mathematics

T2 - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -