Lagrangian Relaxation

Relaxing the integrality restriction is not the only approach to relaxing the problem. An alternative approach to the solution of integer programming problems is to take a set of "complicating" constraints into the objective function in a Lagrangian fashion (with fixed multipliers that are changed iteratively). This approach is known as Lagrangian relaxation. By removing the complicating constraints from the constraint set, the resulting subproblem is frequently considerably easier to solve. The latter is a necessity for the approach to work, because the subproblems must be solved repetitively until optimal values for the multipliers are found. The bound found by Lagrangian relaxation can be tighter than that found by linear programming, but only at the expense of solving subproblems in integers, i.e., only if the subproblems do not have the Integrality Property (a problem has the integrality property if the solution to the Lagrangian problem is unchanged when the integrality restriction is removed). Lagrangian relaxation requires that one understands the structure of the problem being solved in order to then relax the constraints that are "complicating" (Fisher, 1981). A related approach which attempts to strengthen the bounds of Lagrangian relaxation is called Lagrangian decomposition (Guignard and Kim, 1987). This approach consists of isolating sets of constraints so as to obtain separate, easy problems to solve over each of the subsets. The dimension of the problem is increased by creating linking variables which link the subsets. All Lagrangian approaches are problem dependent, and no underlying general theory — applicable to, say, an arbitrary zero-one problem — has evolved.

Most Lagrangian-based strategies provide approaches which deal with special row structures. Other problems may possess special column structure, such that when some subset of the variables are assigned specific values, the problem reduces to one that is easy to solve. Benders' decomposition algorithm fixes the complicating variables and solves the resulting problem iteratively (Benders, 1962). Based on the problem's associated dual, the algorithm must then find a cutting plane (i.e., a linear inequality) which "cuts off" the current solution point but no integer feasible points. This cut is added to the collection of inequalities and the problem is re-solved.

Since each of the decomposition approaches described above provides a bound on the integer solution, they can be incorporated into a branch and bound algorithm, instead of the more commonly used linear programming relaxation. However, these algorithms are special-purpose algorithms in that they exploit the "constraint pattern" or special structure of the problem.