Lagrangean relaxation

Lagrangean relaxations are an alternative appropriate where some of the linear constraints are treated as the complications in an otherwise manageable discrete model. Integrality requirements are explicitly retained in relaxations, emd complicating Unear constraints are dualized, that is, taken to the objective function with appropriate Lagrange multipUers. 

The fourth relaxation of Table 2 illustrates the principle of Lagrangean relaxation, but most of the success with Lagrangean relaxation has derived from problem-spedflc structures. Its power is better illustrated by a classic application. 

Either of the main systems of constraints in (GA) might be thought of as compUcating because deletion of either leaves an easier model where each variable appears in only one constraint. Thus, either system might be first dualized and then dropped. Corresponding Lagrangean relaxations are... 

Any valid choice of multipliers on dualized constraints produces a Lagrangean relaxation, and like all relaxations the optimal objective function value in the relaxation bounds the optimal value of the mtiin problem. However, some choices of constraints to dualize may give rather weak bounds others may yield very strong bounds (see Parker and Rardin 1988, chap. 5 for a full discussion). 

For any fixed dualization strategy, good bounds depend on good multipliers. Successful use of Lagrangean relaxation requires a search where a sequence of Lagrangean relaxations is solved with different multipliers. Results of one relaxation suggest ways to change the multipliers for the next. 

A similar problem to the one considered by Chandra and Fisher (1994) is studied by Fumero and Vercellis (1999). They assume that there is a limited number of vehicles available for product delivery in each time period, whereas no such assumption is made by Chandra and Fisher. They give a different MIP formulation than the one by Chandra and Fisher, and solve it by Lagrangean relaxation. As in Chandra and Fisher (1994), the integrated approach is compared to a decoupled approach in which the production part of the problem is solved first and then the distribution part is solved based on the given solution of production decisions. Similar observations to those obtained by Chandra and Fisher are reported about the value of coordination. 

---