Linear programming relaxation: Difference between revisions

Revision as of 23:39, 24 March 2008

Revision as of 00:04, 25 March 2008

Line 36:

Similar randomized rounding techniques, and derandomized approximation algorithms, may be used in conjunction with linear programming relaxation to develop approximation algorithms for many other problems, as described by Raghavan, Tompson, and Young.

==Branch and bound for exact solutions==

As well as its uses in approximation, linear programming plays an important role in [[branch and bound]] algorithms for computing the true optimum solution to hard optimization problems.

If some variables in the optimal solution have fractional values, we may start a [[branch and bound]] type process, in which we recursively solve subproblems in which some of the fractional variables have their values fixed to either zero or one.

In each step of an algorithm of this type, we consider a subproblem of the original 0-1 integer program in which some of the variables have values assigned to them, either 0 or 1, and the remaining variables are still free to take on either value. In subproblem ''i'', let ''V_i'' denote the set of remaining variables. The process begins by considering a subproblem in which no variable values have been assigned, and in which ''V₀'' is the whole set of variables of the original problem. Then, for each subproblem ''i'', it performs the following steps.

For any subproblem in this process, the LP relaxation provides a valid bound on the solution quality of the optimal integer solution. Therefore, if a subproblem's LP relaxation has a solution quality that is not better than the best integer solution found so far, that branch of the search may be pruned without further searching.

# Compute the optimal solution to the linear programming relaxation of the current subproblem. That is, for each variable ''x_j'' in ''V_i'', we replace the constraint that ''x_j'' be 0 or 1 by the relaxed constraint that it be in the interval [0,1]; however, variables that have already been assigned values are not relaxed.

# If the current subproblem's relaxed solution is worse than the best integer solution found so far, backtrack from this branch of the recursive search.

# If the relaxed solution has all variables set to 0 or 1, test it against the best integer solution found so far and keep whichever of the two solutions is best.

# Otherwise, let ''x_j'' be any variable that is set to a fractional value in the relaxed solution. Form two subproblems, one in which ''x_j'' is set to 0 and the other in which ''x_j'' is set to 1, and recursively search both subproblems.

Although it is difficult to prove theoretical bounds on the performance of algorithms of this type, they can be very effective in practice.

==References==