Iterating Towards A Solution of The Original Problem
The above inequality tells us that if we minimize the maximum value we obtain from the relaxed problem, we obtain a tighter limit on the objective value of our original problem. Thus we can address the original problem by instead exploring the partially dualized problem
-
min s.t.
where we define as
-
max s.t. (1)
A Lagrangian Relaxation algorithm thus proceeds to explore the range of feasible values while seeking to minimize the result returned by the inner problem. Each value returned by is a candidate upper bound to the problem, the smallest of which is kept as the best upper bound. If we additionally employ a heuristic, probably seeded by the values returned by, to find feasible solutions to the original problem, then we can iterate until the best upper bound and the cost of the best feasible solution converge to a desired tolerance.
Read more about this topic: Lagrangian Relaxation
Famous quotes containing the words solution, original and/or problem:
“The truth of the thoughts that are here set forth seems to me unassailable and definitive. I therefore believe myself to have found, on all essential points, the final solution of the problems. And if I am not mistaken in this belief, then the second thing in which the value of this work consists is that it shows how little is achieved when these problems are solved.”
—Ludwig Wittgenstein (1889–1951)
“Man, even man debased by the neocapitalism and pseudosocialism of our time, is a marvelous being because he sometimes speaks. Language is the mark, the sign, not of his fall but of his original innocence. Through the Word we may regain the lost kingdom and recover powers we possessed in the far-distant past.”
—Octavio Paz (b. 1914)
“Theology, I am persuaded, derives its initial impulse from a religious wavering; for there is quite as much, or more, that is mysterious and calculated to awaken scientific curiosity in the intercourse with God, and it [is] a problem quite analogous to that of theology.”
—Charles Sanders Peirce (1839–1914)