Relaxation (approximation)
In mathematical optimization and related fields, relaxation is a modeling strategy. A relaxation is an approximation of a difficult problem by a nearby problem that is easier to solve. A solution of the relaxed problem provides information about the original problem.
For example, a linear programming relaxation of an integer programming problem removes the integrality constraint and so allows non-integer rational solutions. A Lagrangian relaxation of a complicated problem in combinatorial optimization penalizes violations of some constraints, allowing an easier relaxed problem to be solved. Relaxation techniques complement or supplement branch and bound algorithms of combinatorial optimization; linear programming and Lagrangian relaxations are used to obtain bounds in branch-and-bound algorithms for integer programming.
The modeling strategy of relaxation should not be confused with iterative methods of relaxation, such as successive over-relaxation (SOR); iterative methods of relaxation are used in solving problems in differential equations, linear least-squares, and linear programming. However, iterative methods of relaxation have been used to solve Lagrangian relaxations.
Read more about Relaxation (approximation): Definition, Some Relaxation Techniques
Famous quotes containing the word relaxation:
“Worst of all, there is no sign of any relaxation of antisemitism. Logically it has nothing to do with Fascism. But the human race is imitative rather than logical; and as Fascism spreads antisemitism spreads.”
—George Bernard Shaw (1856–1950)