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

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1971
Accession Number
AD0736607

Entities

People

  • Jean L. Goffin

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • C4I
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Bodies
  • California
  • Computational Science
  • Convex Bodies
  • Convex Programming
  • Convex Sets
  • Engineering
  • Linear Programming
  • New York
  • Operations Research
  • Optimization
  • Real Numbers
  • Simplex Method
  • Theorems
  • Topology
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Mathematical Modeling and Probability Theory.
  • Systems Analysis and Design