Anstreicher-Terlaky type monotonic simplex algorithms for linear feasibility problems

F. Bilen, Zsolt Csizmadia, T. Illes

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

Based on the pivot selection rule [Anstreicher, K.M. and Terlaky, T., 1994, A monotonic build-up simplex algorithm for linear programming. Operations Research, 42, 556-561.] we define a new monotonic build-up (MBU) simplex algorithm for linear feasibility problems. An mK upper bound for the iteration bound of our algorithm is given under a weak non-degeneracy assumption, where K is determined by the input data of the problem and m is the number of constraints. The constant K cannot be bounded in general by a polynomial of the bit length of the input data since it is related to the determinants (of the pivot tableau) with the highest absolute value. An interesting local property of degeneracy led us to construct a new recursive procedure to handle strongly degenerate problems as well. Analogous complexity bounds for the linear programming versions of MBU and the first phase of the simplex method can be proved under our weak non-degeneracy assumption.
LanguageEnglish
Pages679-695
Number of pages16
JournalOptimization Methods and Software
Volume22
Issue number4
DOIs
Publication statusPublished - 2007

Fingerprint

Simplex Algorithm
Monotonic
Pivot
Nondegeneracy
Linear programming
Degenerate Problems
Operations research
Simplex Method
Selection Rules
Tableau
Local Properties
Operations Research
Degeneracy
Absolute value
Determinant
Polynomials
Upper bound
Iteration
Polynomial

Keywords

  • feasibility problem
  • Anstreicher-Terlaky type monotonic simplex algorithms
  • degeneracy
  • linear programming

Cite this

Bilen, F. ; Csizmadia, Zsolt ; Illes, T. / Anstreicher-Terlaky type monotonic simplex algorithms for linear feasibility problems. In: Optimization Methods and Software. 2007 ; Vol. 22, No. 4. pp. 679-695.
@article{3e51f0c1867344cd978eca39b0080cbb,
title = "Anstreicher-Terlaky type monotonic simplex algorithms for linear feasibility problems",
abstract = "Based on the pivot selection rule [Anstreicher, K.M. and Terlaky, T., 1994, A monotonic build-up simplex algorithm for linear programming. Operations Research, 42, 556-561.] we define a new monotonic build-up (MBU) simplex algorithm for linear feasibility problems. An mK upper bound for the iteration bound of our algorithm is given under a weak non-degeneracy assumption, where K is determined by the input data of the problem and m is the number of constraints. The constant K cannot be bounded in general by a polynomial of the bit length of the input data since it is related to the determinants (of the pivot tableau) with the highest absolute value. An interesting local property of degeneracy led us to construct a new recursive procedure to handle strongly degenerate problems as well. Analogous complexity bounds for the linear programming versions of MBU and the first phase of the simplex method can be proved under our weak non-degeneracy assumption.",
keywords = "feasibility problem, Anstreicher-Terlaky type monotonic simplex algorithms, degeneracy, linear programming",
author = "F. Bilen and Zsolt Csizmadia and T. Illes",
year = "2007",
doi = "10.1080/10556780701223541",
language = "English",
volume = "22",
pages = "679--695",
journal = "Optimization Methods and Software",
issn = "1055-6788",
number = "4",

}

Anstreicher-Terlaky type monotonic simplex algorithms for linear feasibility problems. / Bilen, F.; Csizmadia, Zsolt; Illes, T.

In: Optimization Methods and Software, Vol. 22, No. 4, 2007, p. 679-695.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Anstreicher-Terlaky type monotonic simplex algorithms for linear feasibility problems

AU - Bilen, F.

AU - Csizmadia, Zsolt

AU - Illes, T.

PY - 2007

Y1 - 2007

N2 - Based on the pivot selection rule [Anstreicher, K.M. and Terlaky, T., 1994, A monotonic build-up simplex algorithm for linear programming. Operations Research, 42, 556-561.] we define a new monotonic build-up (MBU) simplex algorithm for linear feasibility problems. An mK upper bound for the iteration bound of our algorithm is given under a weak non-degeneracy assumption, where K is determined by the input data of the problem and m is the number of constraints. The constant K cannot be bounded in general by a polynomial of the bit length of the input data since it is related to the determinants (of the pivot tableau) with the highest absolute value. An interesting local property of degeneracy led us to construct a new recursive procedure to handle strongly degenerate problems as well. Analogous complexity bounds for the linear programming versions of MBU and the first phase of the simplex method can be proved under our weak non-degeneracy assumption.

AB - Based on the pivot selection rule [Anstreicher, K.M. and Terlaky, T., 1994, A monotonic build-up simplex algorithm for linear programming. Operations Research, 42, 556-561.] we define a new monotonic build-up (MBU) simplex algorithm for linear feasibility problems. An mK upper bound for the iteration bound of our algorithm is given under a weak non-degeneracy assumption, where K is determined by the input data of the problem and m is the number of constraints. The constant K cannot be bounded in general by a polynomial of the bit length of the input data since it is related to the determinants (of the pivot tableau) with the highest absolute value. An interesting local property of degeneracy led us to construct a new recursive procedure to handle strongly degenerate problems as well. Analogous complexity bounds for the linear programming versions of MBU and the first phase of the simplex method can be proved under our weak non-degeneracy assumption.

KW - feasibility problem

KW - Anstreicher-Terlaky type monotonic simplex algorithms

KW - degeneracy

KW - linear programming

UR - http://dx.doi.org/10.1080/10556780701223541

U2 - 10.1080/10556780701223541

DO - 10.1080/10556780701223541

M3 - Article

VL - 22

SP - 679

EP - 695

JO - Optimization Methods and Software

T2 - Optimization Methods and Software

JF - Optimization Methods and Software

SN - 1055-6788

IS - 4

ER -