The LR Solution As A Bound
Of particular use is the property that for any fixed set of values, the optimal result to the Lagrangian Relaxation problem will be no smaller than the optimal result to the original problem. To see this, let be the optimal solution to the original problem, and let be the optimal solution to the Lagrangian Relaxation. We can then see that
The first inequality is true because is feasible in the original problem and the second inequality is true because is the optimal solution to the Lagrangian Relaxation.
Read more about this topic: Lagrangian Relaxation
Famous quotes containing the words solution and/or bound:
“What is history? Its beginning is that of the centuries of systematic work devoted to the solution of the enigma of death, so that death itself may eventually be overcome. That is why people write symphonies, and why they discover mathematical infinity and electromagnetic waves.”
—Boris Pasternak (1890–1960)
“Brave people add up to an aristocracy. The democracy of thou-shalt-not is bound to be a collection of weak men.”
—D.H. (David Herbert)