### Abstract

Language | English |
---|---|

Pages | 679-695 |

Number of pages | 16 |

Journal | Optimization Methods and Software |

Volume | 22 |

Issue number | 4 |

DOIs | |

Publication status | Published - 2007 |

### Fingerprint

### Keywords

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

### Cite this

*Optimization Methods and Software*,

*22*(4), 679-695. https://doi.org/10.1080/10556780701223541

}

*Optimization Methods and Software*, vol. 22, no. 4, pp. 679-695. https://doi.org/10.1080/10556780701223541

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

Research output: Contribution to journal › Article

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 -