Lagrangian relaxation is a generalization of the use of Lagrangian multipliers in classical optimization problems, so we commence with a discussion of such problems before introducing the notion of relaxation.

The so-called “classical constrained optimization problem” applies to real-valued continuous differentiable functions (known as class C₁ functions), f(), g() and is of the form:

or, using vector notation:

Here the expression for z is known as the objective function, the expressions g_i() are known as the constraints, the x_i are variables and the d_i are constants. The constraints in this case are shown as equalities — inclusion of inequalities, which is common, can be handled in a variety of ways, including the use of surrogate variables.

This class of problems can be converted into an unconstrained optimization problem by the use of Lagrangian multipliers. This process often simplifies the task of finding local and global maxima or minima. In the example above, all of the constraints can be moved into the objective function, and we have:

The λ_i components of the expression above are known as the Lagrangian multipliers. Solving the constrained problem then becomes one of maximizing or minimizing a single expression, which in turn requires determination of the introduced multipliers. These may be obtained by finding the differential of the modified objective function with respect to each x_i and equating the result to zero (see Walsh, 1975, for a fuller treatment of the use of Lagrangian multipliers in such problems). Although interpretation of the Lagrangian multiplier values is not a central part of this process, in many instances they can be interpreted as a measure of the importance of the i^th constraint.

As noted earlier, Lagrangian relaxation is a generalization of the above procedure. The idea is to relax the constraints by amending the objective function. The relaxed problem is then solved (if possible) and this can provide a lower (or upper) bound to the set of possible solutions to the original problem. The resultant smaller solution space can then be subjected to more systematic search or attempts can be made to narrow the upper and lower bounds until they meet.

For example, suppose that we are attempting to maximize the simple linear expression:

Additional conditions may be that all the x_j must be greater than or equal to 0, and for problems with discrete solutions, that the solution values must be integers.

We can relax this problem whilst retaining the linear form of the objective function, by moving the constraints into the objective function whilst dropping the inequality, as follows:

If all λ_i=0 the second term in the objective function disappears and thus the constraints play no part in the solution, but if any λ_i>0 the value of the objective function we are trying to optimize is penalized (increased or decreased) when we break the constraints. By adjusting the degree to which the original problem is relaxed, varying the positive vector λ (the Lagrangian) in a systematic manner, and/or by alternative search procedures to the reduced solution space, closer approximations to the original problem can be obtained. Lagrangian relaxation is discussed in some detail in Section 7.4.2.2, which deals with its application to optimum location problems.

The preceding discussion becomes clearer if we take a simplified example. For the purposes of this subsection we use an example provided in the excellent introductory text on combinatorial programming and spatial analysis by Scott (1971):

By dealing with a problem that only involves two variables we can plot this as a graph in which each of the three constraints is shown as a thin line (Figure 7‑3A). Here the horizontal axis is x₁ and the vertical axis, x₂. The three thin colored lines correspond to the three constraints graphed as linear equations g₁ (blue), g₂ (green) and g₃ (red). The solution space is bounded by these three lines (as a result of the inequalities we have defined) and the two axes.

The thick lines show the objective function for increasing values of z. The leftmost line is z=50, then z=55, 60 and 65. The largest possible value the objective function can take is shown by the rightmost thick line, where it just remains inside the two constraint lines illustrated and below the third constraint line.

For this problem the real-valued solution is x₁=4.96 and x₂=2.45, but integer solutions may be obtained by searching the values at the neighboring grid line intersections shown that give the highest value of the objective function, in this instance x₁=4 and x₂=3. This problem can be re-cast, but this time using Lagrangian relaxation applied to a single constraint, as follows:

As can be seen, the third constraint has now been incorporated into the objective function. With this change the objective function can fall outside the boundaries set by the third constraint for all values of λ>0, as shown by the rightmost line (Figure 7‑3B). In this instance the same values for z as above have been used but are augmented by the relaxation element. The relaxation of the third constraint has allowed the objective function to stray beyond the limits of the fully constrained solution. In general, all the inequality constraints can be incorporated into such a relaxation process, giving the more general expression for functions f() and g() as apply in the classical model described earlier.

The above examples have been applied to simple linear expressions, which is not in practice necessary. However, with more complex functions and problems (e.g. constrained shortest path problems, optimum facility location problems) the use of Lagrangian relaxation has been found to be an extremely valuable tool in identifying high quality solutions within acceptable time limits.