Mathematical Description
Given a linear programming problem and of the following form:
-
max s.t.
If we split the constraints in such that, and we may write the system:
-
max s.t. (1) (2)
We may introduce the constraint (2) into the objective:
-
max s.t. (1)
If we let be nonnegative weights, we get penalized if we violate the constraint (2), and we are also rewarded if we satisfy the constraint strictly. The above system is called the Lagrangian Relaxation of our original problem.
Read more about this topic: Lagrangian Relaxation
Famous quotes containing the words mathematical and/or description:
“The most distinct and beautiful statement of any truth must take at last the mathematical form.”
—Henry David Thoreau (1817–1862)
“Once a child has demonstrated his capacity for independent functioning in any area, his lapses into dependent behavior, even though temporary, make the mother feel that she is being taken advantage of....What only yesterday was a description of the child’s stage in life has become an indictment, a judgment.”
—Elaine Heffner (20th century)