Technical Note—The Nested Ball Principle for the Relaxation Method | Zendy

Zvi Drezner | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Technical Note—The Nested Ball Principle for the Relaxation Method

Author(s) -

Zvi Drezner

Publication year - 1983

Publication title -

operations research

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 3.797

H-Index - 140

eISSN - 1526-5463

pISSN - 0030-364X

DOI - 10.1287/opre.31.3.587

Subject(s) - ball (mathematics) , mathematics , linear programming , a priori and a posteriori , feasible region , mathematical optimization , solution set , sequence (biology) , relaxation (psychology) , property (philosophy) , linear inequality , set (abstract data type) , computer science , mathematical analysis , inequality , psychology , philosophy , social psychology , epistemology , biology , genetics , programming language

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research