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
}
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 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 -