Abstract:
Classical and modified Lagrangian bounds for the optimal value of optimization problems with a double decomposable structure are examined. For the class of generalized assignment problems, this property of constraints is used to design a Benders algorithm for solving the modified dual problem. Numerical results are presented that compare the quality of classical and modified bounds.
Key words:Lagrangian bounds in optimization problems, improvement of Lagrangian bounds, generalized assignment problem.