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:
“It is by a mathematical point only that we are wise, as the sailor or the fugitive slave keeps the polestar in his eye; but that is sufficient guidance for all our life. We may not arrive at our port within a calculable period, but we would preserve the true course.”
—Henry David Thoreau (1817–1862)
“I was here first introduced to Joe.... He was a good-looking Indian, twenty-four years old, apparently of unmixed blood, short and stout, with a broad face and reddish complexion, and eyes, methinks, narrower and more turned up at the outer corners than ours, answering to the description of his race. Besides his underclothing, he wore a red flannel shirt, woolen pants, and a black Kossuth hat, the ordinary dress of the lumberman, and, to a considerable extent, of the Penobscot Indian.”
—Henry David Thoreau (1817–1862)