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:
“There is a lot of talk now about metal detectors and gun control. Both are good things. But they are no more a solution than forks and spoons are a solution to world hunger.”
—Anna Quindlen (b. 1953)
“Anybody who knows the difference between the kind of conversation you have walking in the woods and the kind of conversation you have between the segments of a show on Nickelodeon can tell you that quality time exists. Quality time is when you and your child are together and keenly aware of each other. You are enjoying the same thing at the same time, even if it is just being in a room or going for a drive in the car. You are somehow in tune, even while daring to be silent together.”
—Louise Lague (20th century)
“The [nineteenth-century] young men who were Puritans in politics were anti-Puritans in literature. They were willing to die for the independence of Poland or the Manchester Fenians; and they relaxed their tension by voluptuous reading in Swinburne.”
—Rebecca West (1892–1983)
“The original of the picture you inclose, and which I return, was taken from life, and is, I think, a very true one; though my wife, and many others, do not. My impression is that their objection arises from the disordered condition of the hair.”
—Abraham Lincoln (1809–1865)
“There is a delicate balance of putting yourself last and not being a doormat and thinking of yourself first and not coming off as selfish, arrogant, or bossy. We spend the majority of our lives attempting to perfect this balance. When we are successful, we have many close, healthy relationships. When we are unsuccessful, we suffer the natural consequences of damaged and sometimes broken relationships. Children are just beginning their journey on this important life lesson.”
—Cindy L. Teachey. “Building Lifelong Relationships—School Age Programs at Work,” Child Care Exchange (January 1994)