On relaxation methods for systems of linear inequalities

Jan Telgen*

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

10 Citations (Scopus)
17 Downloads (Pure)

Abstract

In their classical papers Agmon and Motzkin and Schoenberg introduced a relaxation method to find a feasible solution for a system of linear inequalities. So far the method was believed to require infinitely many iterations on some problem instances since it could (depending on the dimension of the set of feasible soltions) converge asymptotically to a feasible solution, if one exists. Hence it could not be used to determine infeasibility. Using two lemma's basic to Khachian's polynomially bounded algorithm we can show that the relaxation method is finite in all cases and thus can handle infeasible systems as well. In spite of more refined stopping criteria the worst case behaviour of the relaxation method is not polynomially bounded as examplified by a class of problems constructed here.

Original languageEnglish
Pages (from-to)184-189
Number of pages6
JournalEuropean journal of operational research
Volume9
Issue number2
DOIs
Publication statusPublished - 1 Jan 1982
Externally publishedYes

Fingerprint Dive into the research topics of 'On relaxation methods for systems of linear inequalities'. Together they form a unique fingerprint.

Cite this