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:
“Any solution to a problem changes the problem.”
—R.W. (Richard William)
““Mother” has always been a generic term synonymous with love, devotion, and sacrifice. There’s always been something mystical and reverent about them. They’re the Walter Cronkites of the human race . . . infallible, virtuous, without flaws and conceived without original sin, with no room for ambivalence.”
—Erma Bombeck (20th century)
“Hypocrisy is the essence of snobbery, but all snobbery is about the problem of belonging.”
—Alexander Theroux (b. 1940)