Parametric programming and Lagrangian relaxation: The case of the network problem with a single side-constraint (Q1814154)

This paper introduces a problem of generating the optimal value of the Lagrangian function for a Lagrangian relaxation (LR) of the network problem with a single linear side-constraint. Because of the presence of the side-constraint and the integer restrictions on the decision variables, the linear programming methods cannot be applied to finding the optimal solution of the problem. The author provides approaches based on the parametric programming procedure of \textit{S. I. Gass} and \textit{T. L. Saaty} [Nav. Res. Logist. Quart. 2(1), 39-45 (1955)] for generating the bound determined by the LR of the problem to the optimal value of the objective function.