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

Many practical problems can be formulated as a network problem with a linear side-constraint. Problems of this class would be easy to solve if the side-constraint was not present, and so the technique of Lagrangian relaxation (LR) is often applied as part of the solution strategy. An LR of a problem provides a lower bound (for a minimization problem) on the optimal value of the objective function of the original problem. In this paper approaches for generating this lower bound that are based on the parametric programming procedure of Gass and Saaty are presented.