Accession Number:

AD0736607

Title:

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

Descriptive Note:

[Technical Report, Research Report]

Corporate Author:

CALIFORNIA UNIV BERKELEY

Personal Author(s):

Report Date:

1971-12-01

Pagination or Media Count:

154

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.

Descriptors:

Subject Categories:

  • Theoretical Mathematics
  • Operations Research

Distribution Statement:

[A, Approved For Public Release]