Accession Number : AD0736607

Title :   On the Finite Convergence of the Relaxation Method for Solving Systems of Inequalities,

Corporate Author : CALIFORNIA UNIV BERKELEY OPERATIONS RESEARCH CENTER

Personal Author(s) : Goffin,Jean Louis

Report Date : DEC 1971

Pagination or Media Count : 156

Abstract : 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)

Descriptors :   (*INEQUALITIES, NUMERICAL ANALYSIS), CONVERGENCE, CONVEX SETS, ALGEBRAIC TOPOLOGY, SIMPLEX METHOD, LINEAR PROGRAMMING, THEOREMS

Subject Categories : Theoretical Mathematics
      Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE