Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

Anstreicher-Terlaky type monotonic simplex algorithms for linear feasibility problems

Bilen, F. and Csizmadia, Zsolt and Illes, T. (2007) Anstreicher-Terlaky type monotonic simplex algorithms for linear feasibility problems. Optimization Methods and Software, 22 (4). pp. 679-695. ISSN 1055-6788

Full text not available in this repository. (Request a copy from the Strathclyde author)

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.

Item type: Article
ID code: 28215
Keywords: feasibility problem, Anstreicher-Terlaky type monotonic simplex algorithms, degeneracy, linear programming, Management. Industrial Management
Subjects: Social Sciences > Industries. Land use. Labor > Management. Industrial Management
Department: Strathclyde Business School > Management Science
Related URLs:
    Depositing user: Mrs Caroline Sisi
    Date Deposited: 21 Oct 2010 18:34
    Last modified: 12 Mar 2012 11:20
    URI: http://strathprints.strath.ac.uk/id/eprint/28215

    Actions (login required)

    View Item