Lagrangian relaxation

The main idea of the algorithm of Caroe and Schultz [11] is to decompose a 2S-MILP into its scenarios by Lagrangian relaxation of the non-anticipativity constraints. In a Lagrangian relaxation, constraints are removed and included in the objective function with a penalty term. 

Fisher ML (2004) The Lagrangian Relaxation Method for Solving Integer Programming Problems. Management Science 50 (12) 1861-1871... 

M. L. Fisher. The Lagrangian relaxation method for solving integer programming problems. ManagementSci., 27 1,1981. 

A. M. Geoffrion and R. McBride. Lagrangian relaxation applied to capacitated facility location problems. AIIE Trans., 10 40,1978. 

Mazzola JB, Neebe AW (1999) Lagrangian-relaxation-based solution procedures for a multiproduct capacitated facility location problem with choice of facility type. European Journal of Operational Research 115 285-299... 

Lagrangian Relaxation Algorithm for the Trailer-Assignment Problem 811... 

A Lagrangian relaxation heuristic algorithm that solves the Lagrangian dual problem (35)-(37) is presented next. It uses subgradient optimization to compute the Lagrange multipliers A. 

Geoffrion, A. M. (1974), Lagrangian Relaxation for Integer Programming, Mathematical Programming Study, Vol. 2, pp. 82-114. 

Mathematical programming-based heuristics solve to optimality some mathematical programming approximation of the problem using several techniques (e.g., Lagrangian relaxation algorithm and column generation). 

Zhang, Y., Luh, R Yoneda, K., Kano, T. and Kyoya, Y, 2000. Mixed-model assembly line scheduling using the Lagrangian relaxation technique. EE Transactions, 32(2), 125-134. 

Zhou W, Jin YH (2005) Coordination method for multi-plant supply chain planning optimization based on augmented Lagrangian relaxation. J Tsinghua Univ (Nat Sci) 45 (10) 1324-1327... 

Nie LS, Xu XF, Zhan DC (2006) Collaborative planning in supply chains based on Lagrangian relaxation and genetic algorithm. Comput Integr Manuf Syst 12(11) 1869-1875... 

There are two major approaches to elaboration of computationally efficient algorithms. These are based on Lagrangian relaxation and Bender s decomposition. A short overview of these methods is provided here. Readers are referred to Avriel and Golany (1996) for a detailed coverage of mathematical programming. 

Pirkul and Jayaraman (1998) successfully applied the Lagrangian relaxation problem for the supply chain configuration problem. Similar results have been obtained by Jang et al. (2002) and Amiri (2006). The supply chain configuration model by Pirkul and Jayaraman (1998) locates a specified number of manufacturing facilities and warehouses to minimize fixed and transformation costs subject to customer demand satisfaction and capacity constraints. 

The Optimal Condition Decomposition (OCD), which is a particular case of the Lagrangian relaxation procedure, is applied to overcome the computational cost of solving the monolithic problem, which integrates SC design-retrofitting and product development pipeline management formulations. Further details about this decomposition strategy can be found in Appendix A.7.1. 

Lagrangian relaxation is a technique that is suitable for problems with complicating constraints. The idea is to apply the duality function (see Sect. A. 1.3) to this kind of problems in order to reduce their complexity (Guignard 2003). At this point, it is noteworthy that not all the problem constraints must be included in the Lagrangian function in order to construct the dual function (Bazaraa et al. 1993). The Lagrangian... 

Then, the dual problem can be defined by using the program (A. 8). The Lagrangian relaxation appears when the dual function is evaluated for given values X. and /w. of the multipliers X and ft. Given a structure with complicating constrains, program (A.24) can be decomposed in N subproblems as follows ... 

---