On the Finite Convergence of the Relaxation Method for Solving Systems of Inequalities

摘要

The main concern of this work is to rejuvenate the relaxation method for solving linear inequalities, which uses as primitive the notion of hyperplanes, instead of the more derived concept of vertices or bases. The main result is that the method converges finitely for a wide range of values of the relaxation parameter. The smooth enough property is defined, and it delineates a class of problems where the method works particularly well. It is hoped that the relaxation method might become a powerful alternative to the decomposition, or column generation, techniques for large scale programs in which the theoretical finiteness of the simplex method breaks down to a practical transfiniteness. (Author)