Recovery of primal solutions when using subgradient optimization methods to solve Lagrangian duals of linear programs

Lagrangian duality is a frequently used technique for solving specially structured linear programs or for solving linear programming relaxations of nonconvex discrete or continuous problems within a branch-and-bound approach. In such cases, subgradient optimization methods provide a valuable tool for obtaining quick solutions to the Lagrangian dual problem. However, little is known or available for directly obtaining primal solutions via such a dual optimization process without resorting to penalty functions, to tangential approximation schemes, or the solution of auxiliary primal systems. This paper presents a class of procedures to recover primal solutions directly from the information generated in the process of using pure or deflected subgradient optimization methods to solve such Lagrangian dual formations. Our class of procedure is shown to subsume two existing schemes of this type that have been proposed in the context of pure subgradient approaches under restricted step size strategies.