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:
“All the followers of science are fully persuaded that the processes of investigation, if only pushed far enough, will give one certain solution to each question to which they can be applied.... This great law is embodied in the conception of truth and reality. The opinion which is fated to be ultimately agreed to by all who investigate is what we mean by the truth, and the object represented in this opinion is the real.”
—Charles Sanders Peirce (1839–1914)
“The past is interesting not only for the beauty which the artists for whom it was the present were able to extract from it, but also as past, for its historical value. The same goes for the present. The pleasure which we derive from the representation of the present is due not only to the beauty in which it may be clothed, but also from its essential quality of being present.”
—Charles Baudelaire (1821–1867)
“Abba, dark death is the breaking of a glass.
The dazzled flakes and splinters disappear.
The seal is as relaxed as dirt, perdu.”
—Wallace Stevens (1879–1955)
“In the Original Unity of the First Thing lies the Secondary Cause of All Things, with the Germ of their Inevitable Annihilation.”
—Edgar Allan Poe (1809–1849)
“We attempt to remember our collective American childhood, the way it was, but what we often remember is a combination of real past, pieces reshaped by bitterness and love, and, of course, the video past—the portrayals of family life on such television programs as “Leave it to Beaver” and “Father Knows Best” and all the rest.”
—Richard Louv (20th century)