Content deleted Content added
link relaxation technique |
Outline a little more. This still needs a lot of work. |
||
Line 8:
The resulting relaxation is a [[linear program]], hence the name. This [[Relaxation technique|relaxation technique]] transforms an [[NP-hard]] optimization problem (integer programming) into a related problem that is solvable in [[polynomial time]] (linear programming); the solution to the relaxed linear program can be used to gain information about the solution to the original integer program.
==
The LP-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 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.
==Approximation and integrality gap==
LP relaxation is a standard technique for designing [[approximation algorithm]]s for hard optimization problems. In this application, an important concept is the [[integrality gap]], the maximum ratio between the solution quality of the integer program and its relaxation. Typically, this gap translates into the [[approximation ratio]] of an approximation algorithm.
==Branch and bound==
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.
| |||