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.[1]

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.[2][3][4] However, iterative methods of relaxation have been used to solve Lagrangian relaxations.[a]

  1. ^ Geoffrion (1971)
  2. ^ a b Goffin (1980).
  3. ^ Murty (1983), pp. 453–464.
  4. ^ Minoux (1986).
  5. ^ Minoux (1986), Section 4.3.7, pp. 120–123.
  6. ^ Shmuel Agmon (1954)
  7. ^ Theodore Motzkin and Isaac Schoenberg (1954)
  8. ^ L. T. Gubin, Boris T. Polyak, and E. V. Raik (1969)


Cite error: There are <ref group=lower-alpha> tags or {{efn}} templates on this page, but the references will not show without a {{reflist|group=lower-alpha}} template or {{notelist}} template (see the help page).