Example
Consider the set cover problem, the linear programming relaxation of which was first considered by Lovász (1975). In this problem, one is given as input a family of sets F = {S0, S1, ...}; the task is to find a subfamily, with as few sets as possible, having the same union as F.
To formulate this as a 0-1 integer program, form an indicator variable xi for each set Si, that takes the value 1 when Si belongs to the chosen subfamily and 0 when it does not. Then a valid cover can be described by an assignment of values to the indicator variables satisfying the constraints
(that is, only the specified indicator variable values are allowed) and, for each element ej of the union of F,
(that is, each element is covered). The minimum set cover corresponds to the assignment of indicator variables satisfying these constraints and minimizing the linear objective function
The linear programming relaxation of the set cover problem describes a fractional cover in which the input sets are assigned weights such that the total weight of the sets containing each element is at least one and the total weight of all sets is minimized.
As a specific example of the set cover problem, consider the instance F = {{a, b}, {b, c}, {a, c}}. There are three optimal set covers, each of which includes two of the three given sets. Thus, the optimal value of the objective function of the corresponding 0-1 integer program is 2, the number of sets in the optimal covers. However, there is a fractional solution in which each set is assigned the weight 1/2, and for which the total value of the objective function is 3/2. Thus, in this example, the linear programming relaxation has a value differing from that of the unrelaxed 0-1 integer program.
Read more about this topic: Linear Programming Relaxation
Famous quotes containing the word example:
“Our intellect is not the most subtle, the most powerful, the most appropriate, instrument for revealing the truth. It is life that, little by little, example by example, permits us to see that what is most important to our heart, or to our mind, is learned not by reasoning but through other agencies. Then it is that the intellect, observing their superiority, abdicates its control to them upon reasoned grounds and agrees to become their collaborator and lackey.”
—Marcel Proust (1871–1922)