Solution Quality of Relaxed and Original Programs
The linear programming relaxation of an integer program may be solved using any standard linear programming technique. If the optimal solution to the linear program happens to have all variables either 0 or 1, it will also be an optimal solution to the original integer program. However, this is generally not true, except for some special cases (e.g., problems with totally unimodular matrix specifications.)
In all cases, though, the solution quality of the linear program is at least as good as that of the integer program, because any integer program solution would also be a valid linear program solution. That is, in a maximization problem, the relaxed program has a value greater than or equal to that of the original program, while in a minimization problem such as the set cover problem the relaxed program has a value smaller than or equal to that of the original program. Thus, the relaxation provides a bound on the integer program's solution quality.
In the example instance of the set cover problem described above, in which the relaxation has an optimal solution value of 3/2, we can deduce that the optimal solution value of the unrelaxed integer program is at least as large. Since the set cover problem has solution values that are integers (the numbers of sets chosen in the subfamily), the optimal solution quality must be at least as large as the next larger integer, 2. Thus, in this instance, despite having a different value from the unrelaxed problem, the linear programming relaxation gives us a tight lower bound on the solution quality of the original problem.
Read more about this topic: Linear Programming Relaxation
Famous quotes containing the words solution, quality, relaxed, original and/or programs:
“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)
“The point is, that the function of the novel seems to be changing; it has become an outpost of journalism; we read novels for information about areas of life we don’t know—Nigeria, South Africa, the American army, a coal-mining village, coteries in Chelsea, etc. We read to find out what is going on. One novel in five hundred or a thousand has the quality a novel should have to make it a novel—the quality of philosophy.”
—Doris Lessing (b. 1919)
“I don’t think it is always necessary to take up the anti-colonial—or is it post- colonial?—cudgels against English. What seems to me to be happening is that those people who were once colonized by the language are now rapidly remaking it, domesticating it, becoming more and more relaxed about the way they use it—assisted by the English language’s enormous flexibility and size, they are carving out large territories for themselves within its frontiers.”
—Salman Rushdie (b. 1948)
“An original is a creation
motivated by desire.
Any reproduction of an original
is motivated by necessity ...
It is marvelous that we are
the only species that creates
gratuitous forms.
To create is divine, to reproduce
is human.”
—Man Ray (1890–1976)
“Whether in the field of health, education or welfare, I have put my emphasis on preventive rather than curative programs and tried to influence our elaborate, costly and ill- co-ordinated welfare organizations in that direction. Unfortunately the momentum of social work is still directed toward compensating the victims of our society for its injustices rather than eliminating those injustices.”
—Agnes E. Meyer (1887–1970)