Publication

Abstract : This paper mainly deals with design of Lagrangian decomposition algorithm. Decomposition algorithms are analyzed with respect to various parameters and conditions. Dual decomposition, and more generally Lagrangian relaxation, is a classical method for combinatorial optimization; it has recently been applied to several inference problems. Lagrangian Relaxation (LR) technique decomposes the optimization problem into subproblems; Lagrangian subproblems give the optimal solutions for the optimization problem. The aim of this paper is to identify the control and uncontrolled parameters of the various decomposition techniques which are framed as equality, inequality constraints. Particularly the Lagrangian multipliers added in the objective function of the Lagrangian problem which is acting as “penalty factors”, based on the parameters of the system. It is compared with the other decomposition techniques such as primal decomposition, dual decomposition. A main theme of this paper is that Lagrangian relaxation is obviously applied in conjunction with a wide class of combinatorial algorithms, allowing inference in models that provides the appropriate optimal solutions.