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 language | English |
---|---|
Pages (from-to) | 184-189 |
Number of pages | 6 |
Journal | European journal of operational research |
Volume | 9 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1 Jan 1982 |
Externally published | Yes |