Technical Note—The Nested Ball Principle for the Relaxation Method

Zvi Drezner
Additional contact information
Zvi Drezner: The University of Michigan, Dearborn, Michigan

Operations Research, 1983, vol. 31, issue 3, 587-590

Abstract: In this note, we consider finding a feasible solution to a set of linear inequalities. As is known, there is a ball that can be determined a priori from the problem data knowing the property that it contains a feasible solution if there is one. The relaxation method for solving the problem determines a sequence of shrinking balls that contain a feasible solution if there is one. We show here that if one of the smaller balls is nested inside the first ball, then there is no feasible solution to the problem. This principle is proved to be superior to the existing stopping criterion. We also show that the principle cannot be extended to the Russian method for linear programming.

Keywords: 637 relaxation algorithms; ellipsoid algorithm (search for similar items in EconPapers)
Date: 1983
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.31.3.587 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:31:y:1983:i:3:p:587-590

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().